Theory of Computation (TOC) Seminars
 |
k-Coloring is Faster than Computing the Chromatic Number Tuesday, September 15, 2026 - 4:15pm to 5:15pm We prove that k-coloring on n-vertex graphs has a randomized algorithm running in time (2-eps_k)^n, where eps_k>0 for every fixed k. |
 |
List Decoding Expander-Based Codes (up to capacity, in near-linear time) Tuesday, May 12, 2026 - 4:15pm to 5:15pm We will talk about a new framework based on graph regularity lemmas, for list decoding and list recovery of codes based on spectral expanders. |
 |
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 |
Pages
