Theory of Computation (TOC) Seminars

	Lower bounds for Learning Hamiltonians from Time Evolution Tuesday, April 21, 2026 - 4:15pm to 5:15pm How can we learn about quantum evolutions, given the ability to observe how it interacts with the real world?
	Toy Models of Combinatorial Interpretability Tuesday, April 14, 2026 - 4:15pm to 5:15pm We introduce combinatorial interpretability, a methodology that offers a sandbox for understanding neural computation by analyzing the combinatorial structures in the sign-based categorization of a network's weights and bia
	On zeros and algorithms for disordered systems Tuesday, April 7, 2026 - 4:15pm to 5:15pm Counting and sampling are fundamental algorithmic primitives in high-dimensional statistics and computer science.
	Corners and Communication Complexity Tuesday, March 17, 2026 - 4:15pm to 5:15pm The corners problem is a classical problem in additive combinatorics. A corner is a triple of points (x,y), (x+d,y), (x,y+d). It can be viewed as a 2-dimensional analog of a (one-dimensional) 3-term arithmetic progression.
	Graph-Based Algorithms for Similarity Search: Challenges and Opportunities Friday, March 6, 2026 - 11:00am to 12:00pm
	Interdiction problems and 2-person sequential games: beyond NP-completeness Thursday, March 12, 2026 - 4:15pm to 5:15pm In the Knapsack Problem (KP), a decision maker wants to select items of value V or more to put into a knapsack subject to a weight limit. In the Interdiction Knapsack Problem (IKP), an adversary can block K items from being selected. The adversary’s goal is to pr
	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).

Pages