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. 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 In 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) 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.

Pages