Seminars Sorted by Series

Finding regular subgraphs can be useful. Many results assume a graph is regular or are easier to prove when they are. In 1975, Erdős and Sauer asked for an estimate, for any constant r, on the maximum number of edges an n-vertex graph can have...

A principal challenge in realizing the potential of quantum computing lies in our ability to perform computations fault-tolerantly, in the presence of the noise inherent to quantum devices. Non-Clifford quantum gates, which are analogous to the...

We show that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated in space only $O(\sqrt{t \log t})$. This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time $t$ in $O(t...

Two central results in modern complexity theory can be summed up as follows:

1. Everything provable is provable in zero knowledge (NP ⊆ CZK); and
2. Everything provable is locally checkable (NP = PCP[log n, 1]).

In a pair of recent works, we show how to...

In both computer science and economics, efficiency is a cherished property. The field of algorithms is almost solely focused on their efficiency. The goal of AI research is to increase efficiency by reducing human labor.  In economics, the main...

Private Information Retrieval (PIR) is a method for a user to interact with t non-colluding servers and read some entry of a database of size n without revealing to the servers anything about which entry of the database was read. After a long line...

Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings...

In theoretical computer science, an increasingly important role is being played by sparse high-dimensional expanders (HDXs), of which we know two main constructions: "building" HDXs [Ballantine'00, ...] and "coset complex" HDXs [Kaufman--Oppenheim...

This talk will be about two related results, one in complexity theory and one in learning.

On the learning side, we investigate the sample complexity of smooth boosters - These are boosting algorithms that do not place too much weight on any given...

I will describe a recent extension of the classical PAC (Probably Approximately Correct) learning framework [Vapnik and Chervonenkis, 1970s; Valiant, 1980s]. This extension makes it possible to model a wide range of common and practical data...

Abstract: A linear extension of $P$ is a linear ordering compatible with the poset relations. Let $p(x< y), p(y < x))$ and $\delta(P)$ be the maximum value of $\delta(x, y)$ over all $x, y$ in $P$. The following two conjectures about $\delta(P)$ are both well-known:

1. (The "1/3-2/3 Conjecture") $\delta(P) \geq \frac{1}{3}$ whenever $P$ is not a chain.
2. (The "Kahn-Saks Conjecture") $\delta(P) \to \frac{1}{2}$ as $w(P) \to \infty$ (where $w(P)$ is the maximum size of an antichain in $P$).

While still far from either of these, we prove a number of conditions for $\delta(P) \to \frac{1}{2}$ and $\delta(P) \geq \frac{1}{e} - o(1)$, using a mix of geometric and probabilistic techniques. Joint with Jeff Kahn.

What is the cost of a task if we have to perform it many times? Can we achieve economies of scale? Such "direct-sum problems" play a central role in many areas of mathematics, physics and computer science. Protagonistic problems of this kind are...

In this work, we develop a new method for proving lower bounds for static data structures in the classical cellprobe model of Yao. Our methods give the strongest known lower bounds for any explicit problem in this model (quadratically stronger for...

In 1984 W. B. Johnson and J. Lindenstrauss showed that a random projection of an arbitrary point set S into low-dimensional space is approximately distance-preserving, as long as S is of size at most exponential in the target dimension. The...

In the NISQ era, where noise limits device coherence times, we are fundamentally constrained to shallow quantum computation. This talk will explore the power, limitations, and learnability of the $QAC^0$ circuit class--i.e. the family of constant...

In this talk, I will describe our construction of the first explicit lossless vertex expanders. These are graphs where every small subset of vertices has about as many neighbors as their sparsity allows. Previously, the strongest known explicit...

Matrix-perturbation bounds quantify how the spectral characteristics of a baseline matrix A change under additive noise E. Classical results, including Weyl’s inequality for eigenvalues and the Davis–Kahan theorem for eigenvectors and eigenspaces...

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)$. The related Beck-Fiala conjecture states...

Over 40 years ago, Karp, Upfal, and Wigderson posed a central open question in parallel computation: how many adaptive rounds are needed to find a basis of a matroid using only independence queries? Their pioneering work gave an upper bound of $O(...

Large language models (LLMs) sometimes generate statements that are plausible but factually incorrect—a phenomenon commonly called "hallucination." We argue that these errors are not mysterious failures of architecture or reasoning, but rather...

In this talk, I will explore the fascinating landscape of assumptions in quantum cryptography—especially, how little we need to assume to build secure quantum protocols. We will cover key cryptographic primitives including quantum encryption...

High-dimensional expanders (HDX) are a generalization of expander graphs which have seen various applications in coding theory, PCPs, pseudorandomness, derandomization, approximate sampling, and beyond. One technique for proving a complex is an HDX...

Direct-product testers” are used in the design of (some) probabilistically checkable proofs (PCPs), which, in turn, play a fundamental role in modern complexity theory and cryptography. We investigate the direct-product testability of certain...

In this talk, I will discuss the solution to several problems in two closely related settings: set families in 2^[n] with many disjoint pairs, and low-rank matrices with many zero entries.

Highlights include a resolution of an old question of Daykin...

The Linear Ordering Principle (LOP) is a total search problem that generalizes the task of finding the minimum element of a given order to settings in which the order need not be total. Building on this, Korten and Pitassi (FOCS 2024) introduced the...

The very first result ever proved about tournaments is due to Rédei, who nearly 100 years ago proved that every tournament contains a Hamiltonian directed path. Since then, questions and results about directed paths in tournaments have become a...

We revisit the question of whether it is possible to build succinct non-interactive arguments (SNARGs) for all of NP under standard cryptographic assumptions. In particular, we give a candidate non-adaptive SNARG for NP and prove its soundness under...

We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notions such as minimum distance, list-decoding, list-recovery, and perfect...

We define and study an extension of the notion of the VC-dimension of a hypergraph and apply it to establish a Tverberg type theorem for unions of convex sets. We also prove a new Radon type theorem for unions of convex sets, settling an open...

Note: This talk will involve quantum computing, cryptography, and representation theory, but no background in any of these will be necessary to understand it. I'll introduce everything from the basics.

Aaronson, Atia, and Susskind (2020) established...

The development of set theory in the 20th century was like the invention of a "mathematical telescope", through which we can observe all kinds of infinite sets and their interactions. In quite the opposite direction, bounded arithmetic serves as a...

What is the relative computational power of time and space? Tree evaluation (TreeEval) has become a central problem in understanding this question, especially after its application by Williams (STOC 2025, IAS CSDM seminar 9/23/25) to prove a...

We construct very efficient argument systems for proving the correctness of bounded-space computations, based on the existence of one-way functions. Our argument system applies to general computations running in time T and space S. The communication...

We consider the problem of explicitly constructing binary linear codes achieving the optimal rate-distance tradeoff.  In 2017, Ta-Shma gave an almost-optimal construction in the low-rate regime, i.e., he gave a construction of binary linear codes...