Algorithms and Complexity Seminars

Yuval Filmus: Twenty (simple) questions
Thursday, March 2, 2017 - 4:00pm to 5:00pm
Alice chooses a number x in {1,...,n} according to a known distribution \mu, and Bob identifies x using Yes/No questions. Bob's goal is to minimize the expected number of questions until x is identified, and his optimal strategy uses about H(\mu) questions on average.
Nika Haghtalab: Opting Into Optimal Matchings
Wednesday, March 1, 2017 - 4:00pm to 5:00pm

Kidney transplant is sometimes the best treatment for people who suffer from chronic kidney disease.

Ilias Diakonikolas: A New Approach for Distribution Testing
Wednesday, October 12, 2016 - 4:00pm to 5:00pm

We study problems in distribution property testing: Given sample access to one or more unknown discrete distributions, we want to determine whether they have some global property or are

A Nearly Tight Sum of Squares Lower Bound for Planted Clique
Wednesday, April 27, 2016 - 4:00pm to 5:00pm

Abstract: We prove that with high probability over the draw of a graph from the Erdos-Renyi distribution G(n,1/2), the ~n^d time, degree d sum of squares relaxation for the clique problem gives a value of ~n^{1/2-o(1)} for any d = o(\log(n)).

Rati Gelashvili: Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States
Wednesday, May 20, 2015 - 4:00pm to 5:00pm

Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules.

Shay Solomon: Dynamic Maximum Matching and Related Problems
Thursday, May 7, 2015 - 4:00pm to 5:00pm

Graph matching is one of the most well-studied problems in combinatorial optimization, with applications ranging from scheduling and object recognition to numerical analysis and computational chemistry.

TALK: JM Landsberg: Geometry and the Complexity of Matrix Multiplication
Wednesday, April 29, 2015 - 4:00pm to 5:00pm

Ever since Strassen showed that nxn matrices can be multiplied using O(n^2.81) arithmetic operations as opposed to the usual

Sergey Gorbunov: Leveled Fully Homomorphic Signatures from Standard Lattices
Wednesday, April 22, 2015 - 4:00pm to 5:00pm

Abstract: In a homomorphic signature scheme, a user Alice signs some large dataset $x$ using her secret signing key and uploads the signed data to an untrusted remote server.

Henry Yuen: Parallel repetition for entangled games via fast quantum search
Wednesday, April 15, 2015 - 4:00pm to 5:00pm

We give improved parallel repetition theorems for multiplayer, one-round games with entangled players, when the inputs to the players are uncorrelated.

Grigory Yaroslavtsev:Near Optimal LP Rounding for Correlation Clustering on Complete Graphs
Thursday, April 9, 2015 - 3:15pm to 4:15pm

Introduced about 10 years ago by Bansal, Blum and Chawla, correlation clustering has become one of the standard techniques in machine learning and data mining. This due to several advantages of correlation clustering as compared to other standard clustering methods (e.g. k-means):


Subscribe to Algorithms and Complexity Seminars