Theory of Computation (TOC) Seminars
 |
Can we speed safely? Tuesday, December 9, 2025 - 4:15pm to 5:15pm Often, algorithmic tasks can be greatly sped up for inputs that are promised to have certain structural properties, such as inputs that are assumed to be random, or to come from restricted classes of graphs. |
 |
Redundancy is all you need (for CSP sparsification) Tuesday, October 28, 2025 - 4:15pm to 5:15pm Constraint Satisfaction Problems (CSPs) form a broad and central class in the theory of computation. I will describe a recent result (with J. |
 |
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 |
Pages
