Theory of Computation (TOC) Seminars
 |
Introducing Algorithmic Thinking Theory for Foundation Models Tuesday, October 14, 2025 - 4:15pm to 5:15pm The last few months have witnessed tremendous advances on Large Language Model (LLM) reasoning capabilities with Gemini and GPT winning a gold medal at the International Mathematical Olympiad (IMO) [1] and International Collegiate Programming Contest (ICPC) [2]. |
 |
On Beck-Fiala and Komlós Conjectures Tuesday, October 7, 2025 - 4:15pm to 5:15pm A conjecture of Komlós states that the discrepancy of any collection of unit vectors is O(1), i.e., for any matrix A with unit columns, there is a vector x with -1,1 entries such that |Ax|_\infty = O(1). |
 |
Sparsification of 1-in-3-SAT Tuesday, September 16, 2025 - 4:15pm to 5:15pm I will introduce a new notion of sparsification that doesn't drop constraints but merges variables. Using tools from additive combinatorics, I will then show that 1-in-3-SAT admits a sub-quadratic sparsifier. |
 |
A New Paradigm for Learning with Distribution Shift Tuesday, September 9, 2025 - 4:15pm to 5:15pm We revisit the fundamental problem of learning with distribution shift, where a learner is given labeled samples from training distribution D, unlabeled samples from test distribution D′ and is asked to output a classifier with low test error. |
 |
Explicit Lossless Vertex Expanders Tuesday, September 23, 2025 - 4:15pm to 5:15pm We give the first explicit construction of lossless vertex expanders. These are d-regular graphs where every small set S of vertices has (1-eps)d|S| distinct neighbors. |
 |
Deciding high-dimensional sub-Gaussian-ness in polynomial time Tuesday, May 6, 2025 - 4:15pm to 5:15pm Given samples from a probability distribution, can efficient algorithms tell whether the distribution has heavy or light tails? |
 |
Learning Multi-Index Models Tuesday, April 15, 2025 - 4:15pm to 5:15pm Multi-index models (MIMs) are functions that depend on the projection of the input onto a low-dimensional subspace. |
 |
How to Securely Implement Cryptography in Deep Neural Networks Tuesday, April 22, 2025 - 4:15pm to 5:15pm The wide adoption of deep neural networks (DNNs) raises the question of how can we equip them with a desired cryptographic functionality (e.g., to decr |
 |
Simulating Time With Square-Root Space Tuesday, April 8, 2025 - 4:15pm to 5:15pm |
 |
Rapid Mixing at the Uniqueness Threshold Tuesday, March 18, 2025 - 4:15pm to 5:15pm Over the past decades, a fascinating computational phase transition has been identified in sampling from Gibbs distributions. |
Pages
