Theory of Computation (TOC) Seminars

Coboundary Expansion Inside Chevalley Coset Complex HDXs
Tuesday, December 10, 2024 - 4:15pm to 5:15pm
Recent major results in property testing and PCPs were unlocked by moving to high-dimensional expanders (HDXs) constructed from C_d-type buildings, rather than the long-known A_d-type ones.
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:

Pages

Subscribe to Theory of Computation (TOC) Seminars