# Algorithms and Complexity Seminars

 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. Henry Yuen: Parallel repetition for entangled games via fast quantum searchWednesday, April 15, 2015 - 4:00pm to 5:00pmWe 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:15pmIntroduced 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):