Theory of Computation (TOC) Seminars

Surbhi Goel: Computational Complexity of Learning Neural Networks over Gaussian Marginals
Tuesday, December 15, 2020 - 4:00pm to 5:00pm
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
wants to measure n quantum states, in a way that damages the states
only by a little) and differential privacy (where one wants to query a

Jelani Nelson: Heavy Hitters via Cluster-Preserving 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 small-space algorithms and lower bounds for constant-depth circuits.
The 4/3 Additive Spanner Exponent is Tight
Thursday, December 10, 2015 - 4:00pm to 5:00pm
Mary Wootters: Repairing Reed-Solomon Codes
Monday, December 7, 2015 - 4:00pm to 5:00pm

A fundamental fact about polynomial interpolation is that k evaluations of a degree-(k-1) polynomial f(x) are sufficient to determine f(x).  This is also necessary in a strong sense: given k-1 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 one-way 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 Ben-David.​

Virginia Vassilevska Williams: Fine-Grained Algorithms and Complexity
Tuesday, November 10, 2015 - 4:00pm to 5:00pm


Subscribe to Theory of Computation (TOC) Seminars