Theory of Computation (TOC) Seminars
 |
A New Approach to Optimal Spectral Gaps Tuesday, December 3, 2024 - 4:15pm to 5:15pm It was conjectured by Alon in the 1980s that random d-regular graphs have the largest possible spectral gap (up to negligible error) among all d-regular graphs. This conjecture was proved by Friedman in 2004 in major tour de force. |
 |
Recent Advances in Differential Privacy under Continual Observation Tuesday, November 26, 2024 - 4:15pm to 5:15pm Differential privacy is one of the most popular definitions of privacy, |
 |
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 |
Pages
