Theory of Computation (TOC) Seminars

	Adaptivity Does Not Help: Nearly Tight Lower Bounds for Boolean Monotonicity Testing Tuesday, April 28, 2026 - 4:15pm to 5:15pm Monotonicity testing asks: given a Boolean function f: {0,1}^n -> {0,1}, how many queries are needed to distinguish whether f is monotone or far from monotone? For nonadaptive algorithms, the query complexity was pinned down at \sqrt{n}.
	Calibration in the Age of AI: From Prediction to Decision Making to AI Assisted Research Tuesday, May 5, 2026 - 4:15pm to 5:15pm Calibration serves as a trustworthy interface between prediction and decision making, and has (in my opinion) been getting only more important and interesting as a research topic as AI agents become commonplace.
	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.

Pages