# Algorithms and Complexity Seminars

 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. Inparticular, there exist properties for which there is an exponential gap Dean Doron: Explicit two-source extractors for near-logarithmic min-entropyWednesday, March 15, 2017 - 4:00pm to 5:00pmIn this talk, we show an explicit construction of extractors for two independent sources of near-logarithmic min-entropy.Previous constructions required either polylog(n) min-entropy or more than two sources. Yuval Filmus: Twenty (simple) questionsThursday, March 2, 2017 - 4:00pm to 5:00pmAlice 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 MatchingsWednesday, March 1, 2017 - 4:00pm to 5:00pmKidney transplant is sometimes the best treatment for people who suffer from chronic kidney disease. Ilias Diakonikolas: A New Approach for Distribution TestingWednesday, October 12, 2016 - 4:00pm to 5:00pmWe 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 CliqueWednesday, April 27, 2016 - 4:00pm to 5:00pmAbstract: 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 StatesWednesday, May 20, 2015 - 4:00pm to 5:00pmPopulation protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules. Shay Solomon: Dynamic Maximum Matching and Related ProblemsThursday, May 7, 2015 - 4:00pm to 5:00pmGraph 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:00pmEver 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:00pmAbstract: 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.