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

Pages