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):

Pages