Theory of Computation (TOC) Seminars

Estimating the Longest Increasing and Longest Common Subsequences
Tuesday, November 15, 2022 - 4:15pm to 5:15pm
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
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.


Subscribe to Theory of Computation (TOC) Seminars