Swastik Kopparty: Fast algorithms for polynomials over all finite fields via the Elliptic Curve Fast Fourier Transform (ECFFT) Tuesday, October 5, 2021  4:00pm to 5:00pm 

Surbhi Goel: Computational Complexity of Learning Neural Networks over Gaussian Marginals Tuesday, December 15, 2020  4:00pm to 5:00pm Abstract: 

Scott Aaronson: Gentle Measurement of Quantum States and Differential Privacy Tuesday, November 20, 2018  4:00pm to 5:00pm We prove a surprising connection between gentle measurement (where one 

Jelani Nelson: Heavy Hitters via ClusterPreserving Clustering Tuesday, November 15, 2016  4:00pm to 5:00pm Abstract: In the "heavy hitters" or "frequent items" problem, one must process a stream of items and report those items that occur frequently. For example, a telecommunications company may wish to find popular destination IP addresses in a packet stream across one of their links, 

Raghu Meka: Pseudorandomness old problems, new methods, and current challanges Thursday, March 3, 2016  2:45pm to 3:45pm Abstract: In this talk I will survey recent results on two classical questions in complexity theory: derandomizing smallspace algorithms and lower bounds for constantdepth circuits. 

The 4/3 Additive Spanner Exponent is Tight Thursday, December 10, 2015  4:00pm to 5:00pm 

Mary Wootters: Repairing ReedSolomon Codes Monday, December 7, 2015  4:00pm to 5:00pm A fundamental fact about polynomial interpolation is that k evaluations of a degree(k1) polynomial f(x) are sufficient to determine f(x). This is also necessary in a strong sense: given k1 evaluations of f, we learn nothing about f(a) for any k'th point a. We s 

Gillat Kol: Interactive Information Theory Thursday, December 3, 2015  4:00pm to 5:00pm Abstract: In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study oneway data transmission problems over different channels, both noisy and noiseless. That paper initiated the 

Omri Weinstein: Interactive Information Complexity and Applications Monday, November 16, 2015  4:00pm to 5:00pm Abstract: Over the past three decades, communication complexity has been extensively used to capture the fundamental limitations in diverse areas of theoretical computer science and modern computing systems. 

Robin Kothari: Separations in Query Complexity Using Cheat Sheets Tuesday, November 17, 2015  4:00pm to 5:00pm Abstract: 2015 has been an exciting year for query complexity. I'll survey some of the breakthroughs made this year and then talk about some very recent work with my collaborators Scott Aaronson and Shalev BenDavid. 