Theory of Computation (TOC) Seminars
 |
Overparametrized systems: from Smale's 17th problem to two-layer neural networks Tuesday, March 11, 2025 - 4:15pm to 5:15pm Training modern machine learning models requires to optimize highly non-convex risk function and yet simple gradient-based methods are able to find global minima for very high-dimensional problems. |
 |
Pseudorandom Correlation Generators Tuesday, March 4, 2025 - 4:15pm to 5:15pm Correlated secret randomness is an important resource for many cryptographic applications. |
 |
Good Locally Testable Codes Tuesday, February 25, 2025 - 4:15pm to 5:15pm An error-correcting code is locally testable (LTC) if there is a random tester that reads only a small number of bits of a given word and decides whether the word is in the code, or at least close to it. |
 |
On the Complexity of Neural Computation in Superposition Tuesday, February 18, 2025 - 4:15pm to 5:15pm Recent advances in neural networks interpretability suggest that superposition, the ability of a network to represent many more features than it has neurons, is a key mechanism underlying how neural networks compute. |
 |
"Local-to-Global" Theorems on High Dimensional Expanders Tuesday, February 11, 2025 - 4:15pm to 5:15pm |
 |
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 |
Pages
