Seminars Sorted by Series

A function $f : \mathbb{F}_2^n \to \mathbb{F}_2^n$ is linear if $f(x+y)=f(x)+f(y)$ for all pairs $(x,y)$.

Suppose $f$ is "a bit linear" -- say, $f(x+y)=f(x)+f(y)$ for 1% of pairs $(x,y)$.  Must $f$ agree with a truly linear function a positive...

The Tree Evaluation Problem has emerged in the past decade as a leading candidate for separating logspace from polynomial time. In this talk we will introduce the problem, as well as the context behind its introduction and conjectured hardness. We...

In this talk, I will discuss progress on showing hardness of the Minimum Circuit Size Problem (MCSP). The computational complexity of MCSP is a longstanding mystery, dating back as far as Levin's seminal work on NP-completeness in 1973. Over the...

Consider an oracle which takes a point $x$ and returns the minimizer of a convex function $f$ in an $\ell_2$ ball of radius $r$ around $x$. While it is straightforward to show that $\approx r^{-1}$ queries to this oracle suffice to minimize $f$ to...

Over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated...

Where are the hard problems? In the absence of a proof of P ≠ NP, researchers have spent years proving unconditional lower bounds for constrained models of computation. In time, a distinct theme arose: random problems (in particular random...

In this talk, we will show that the supremum of any centered Gaussian process can be approximated to any arbitrary accuracy by a finite dimensional Gaussian process where the dimension of the approximator is just dependent on the target error. As a...

In distributed certification, our goal is to certify that a network has a certain desired property, e.g., the network is connected, or the internal states of its nodes encode a valid spanning tree of the network. To this end, a prover generates...

A dictionary data structure maintains a set of at most $n$ keys from the universe $[U]$ under key insertions and deletions, such that given a query $x\in[U]$, it returns if $x$ is in the set. Some variants also store values associated to the keys...

About 20 years ago, Gurvits developed the notion of polynomial capacity to give a simple proof of the famous van der Waerden lower bound on the permanent of a doubly stochastic matrix. Since then, similar techniques have led to various other...

A sparsification of a structure, with respect to a class of queries, produces a compressed representation of the structure while answering every query in the class approximately correctly. The seminal example of sparsification is "graph...

Subsets $A$ of an abelian group with a small doubling $|A+A|/|A|$ have been extensively studied, and results of Freiman, Ruzsa and Green give fundamental structural descriptions of such sets. These have important applications across combinatorics...

In this talk, I will discuss lower bounds for a certain set-multilinear restriction of algebraic branching programs. The significance of the lower bound and the model is underscored by the recent work of Bhargav, Dwivedi, and Saxena (2023), which...

In this talk, we will present a new approach for approximating large independent sets when the input graph is a one-sided expander—that is, the uniform random walk matrix of the graph has second eigenvalue bounded away from 1. Specifically, we show...

The central problem of physics and quantum chemistry is to find the ground state energy of some physical system governed by quantum mechanics.  In mathematical terms, this means finding the lowest eigenvalue of some linear operator on a vector space...

In this talk, I'll show that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. This settles a long-standing open question in the area of low-degree testing, yielding...

We consider the problem of sorting a set of items having an unknown total order by doing binary comparisons of the items, given the outcomes of some pre-existing comparisons. We present a simple new algorithm with a running time of O(m + n + log T)...

A common theme in mathematics is that limits of finite objects are well behaved. This allows one to prove many theorems about finitely approximable objects, while leaving the general case open --- examples for this are Gottschalk's conjecture...

The well-known Zig-Zag product and related graph operators, like derandomized squaring, are fundamentally combinatorial in nature. Classical bounds on their behavior often rely on a mix of combinatorics and linear algebra. However, these traditional...

Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved.  What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving...

The theory of probabilistically checkable proofs (PCPs) shows how to encode a proof for any theorem into a format where the theorem's correctness can be verified by making only a constant number of queries to the proof. The PCP Theorem [ALMSS] is a...

Recent advancements in quantum error correction have led to breakthroughs in good quantum low-density parity-check (qLDPC) codes, which offer asymptotically optimal code rates and distances. However, several open questions remain, including the...

Tree decompositions, and in particular path decompositions, are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”...

A dot-product proof is a simple probabilistic proof system in which the verifier decides whether to accept an input vector based on a single linear combination of the entries of the input and a proof vector. I will present constructions of linear...

In quantum complexity theory, QMA and QCMA represent two different generalizations of NP. Both are defined as sets of languages whose Yes instances can be efficiently checked by a quantum verifier that is given a witness. With QMA the witness can be...

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send the k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication? This is the...

What can be said about a system of polynomial equations over a finite field if its number of solutions deviates from that of a random system? Answer: Roughly, one of the polynomials (or a linear combination thereof) can be written in terms of “few”...

The satisfiability problem for Constraint Satisfaction Problems (CSPs) asks whether an instance of a CSP has a fully satisfying assignment, i.e., an assignment that satisfies all constraints. This problem is known to be in class P or is NP-complete...

The recent breakthrough of Limaye, Srinivasan and Tavenas (LST) gave the first super-polynomial lower bounds against low-depth algebraic circuits, for any field of zero (or sufficiently large) characteristic. It was an open question to extend this...

Q1: A fundamental result in coding theory, known as the Plotkin bound, suggests that a binary code can tolerate up to ¼ fraction of adversarial corruptions. Can we design codes that handle more errors if we allow interaction between the sender and...

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