Clément Canonne: Fifty Shades of Adaptivity (in Property Testing) Wednesday, April 5, 2017  4:00pm to 5:00pm Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap 

Dean Doron: Explicit twosource extractors for nearlogarithmic minentropy Wednesday, March 15, 2017  4:00pm to 5:00pm


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 ErdosRenyi 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/2o(1)} for any d = o(\log(n)). 

Rati Gelashvili: PolylogarithmicTime Leader Election in Population Protocols Using Polylogarithmic States Wednesday, May 20, 2015  4:00pm to 5:00pm Population protocols are networks of finitestate 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 wellstudied 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. 