Theory of Computation (TOC) Seminars

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.

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

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.

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

Constraint Satisfaction Problems (CSPs) form a broad and central class in the theory of computation. I will describe a recent result (with J.

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).

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.

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

Over the past decades, a fascinating computational phase transition has been identified in sampling from Gibbs distributions.

Correlated secret randomness is an important resource for many cryptographic applications.

Recent advances in neural networks interpretability suggest that superposition, the ability of a network to represent many more features than it has neurons, is a key mechanism underlying how neural networks compute.