Theory of Computation (TOC) Seminars

	Vizing’s Theorem in Near-Linear Time Tuesday, November 19, 2024 - 4:15pm to 5:15pm In his classic result, Vizing (1964) proved that any graph of maximum degree ∆ can be edge colored using at most ∆+1 different colors.
	Learning to Defer in Content Moderation: The Human-AI Interplay Tuesday, October 8, 2024 - 4:15pm to 5:15pm Ensuring successful content moderation is vital for a healthy online social platform where it is necessary to responsively remove harmful posts without j
	Near Optimal Alphabet-Soundness Tradeoff PCPs Tuesday, September 24, 2024 - 4:15pm to 5:15pm We show a nearly optimal
	Learning in Strategic Environments: from Calibrated Agents to General Information Asymmetry Tuesday, September 17, 2024 - 4:15pm to 5:15pm In this talk I will discuss learning in principal-agent games where there is information asymmetry between what the principal and what the agent know about each other’s chosen actions.
	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.

Pages