![]() |
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 two-source extractors for near-logarithmic min-entropy 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 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. |