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