Seminars Sorted by Series

Our goal is to develop a generic framework for converting modern gradient-descent based optimization algorithms into mechanisms where inputs come from self-interested agents.

We focus on aggregating preferences from n players in a context without...

Over a high-dimensional vector space $F_p^n $over a fixed finite field $F_p$, the inverse theorem for the Gowers norm asserts that a bounded function f on this space that has a large Gowers $U^{k+1}$ norm, must necessarily correlate with a phase...

Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that matrices can be multiplied in nearly-linear time. If true, this conjecture would yield similarly-fast...

Let K be a convex body in $R^n$. In some cases (say when K is a cube), we can tile $R^n$ using translates of K. However, in general (say when K is a ball) this is impossible. Nevertheless, we show that one can always cover space "smoothly" using...

Efficient verification of computation is fundamental to computer science and is at the heart of the P vs. NP question. Recently it has had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud...

Tree 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”. Exhibiting a particular kind of a tree...

In the minimum cost set cover problem, a set system is given as input, and the goal is to find a collection of sets with minimum cost whose union covers the universe. This NP-hard problem has long been known to admit logarithmic approximations...

A central goal of physics is to understand the low-energy solutions of quantum interactions between particles. This talk will focus on the complexity of describing low-energy solutions; I will show that we can construct quantum systems for which the...

Suppose you have a set S of integers from {1 , 2 , … , N} that contains at least N / C elements. Then for large enough N , must S contain three equally spaced numbers (i.e., a 3-term arithmetic progression)?

In 1953, Roth showed that this is indeed...

Extremal combinatorics is a central research area in discrete mathematics. The field can be traced back to the work of Turán and it was established by Erdős through his fundamental contributions and his uncounted guiding questions. Since then it has...

Several classical results in Ramsey theory (including famous theorems of Schur, van der Waerden, Rado) deal with finding monochromatic linear patterns in two-colourings of the integers.  Our topic will be quantitative extensions of such results.  A...

A CSS quantum code $\mathcal{C} = (W_1, W_2)$ is a pair of orthogonal subspaces in $\mathbb{F}_2^n$. The distance of $\mathcal{C}$ is the smallest hamming weight of a vector in $W_1^{\perp}-W_2$ or $W_2^{\perp}-W_1$. A large distance roughly means...

Erdős' unit distance problem and his related distinct distances problem are arguably the best known open problems in discrete geometry.

They ask for the maximum possible number of unit distances, and the minimum possible number of distinct...

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem’s space  complexity as it constitutes the main route...

A finite set system is union-closed if for every pair of sets in the system their union is also in the system.  Frankl in 1979 conjectured that for any such system there exists an element which is contained in ½ of the sets in that system (the only...

In a vertex expanding graph, every small subset of vertices neighbors many different vertices. Random graphs are near-optimal vertex expanders; however, it has proven difficult to create families of deterministic near-optimal vertex expanders, as...

It is widely believed that the physics of diffraction imposes certain fundamental limits on the resolution of an optical system. In this work we study the diffraction limit as a statistical inverse problem in increasingly more realistic mathematical...

In this talk, I will present the following two connections between private optimization and statistical physics, both via the problem of approximating a given covariance matrix with a low-rank matrix:

1. An efficient algorithm to privately compute a...

We will discuss a generalization of the celebrated Minimax Theorem (von Neumann, 1928) for binary zero-sum games. A simple game which fails to satisfy Minimax is Ephraim Kishon's “Jewish Poker” (see [1,2] below). In this game, each player picks a...

In 1948, Shannon used a probabilistic argument to show the existence of codes achieving channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major...

In this work we prove a high dimensional analogue of the beloved Goldreich-Levin  theorem (STOC 1989), which is the first local list-decoding algorithm.  We consider the following algorithmic problem: given oracle access to a function $f: Z_q^m...

While the notion of spectral gap is a fundamental and very useful feature of reversible Markov chains, there is no standard analogue of this notion for nonreversible chains. In this talk, I will present a simple proposal for spectral gap of...

Strong spatial mixing (SSM) is an important and widely studied quantitative notion of "correlation decay" for a variety of natural distributions arising in statistical physics, probability theory, and theoretical computer science. One of the most...

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In...

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits. Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested approaching this problem by proving that depth...

A recent line of work has shown a surprising connection between multicalibration, a multi-group fairness notion, and omniprediction, a learning paradigm that provides simultaneous loss minimization guarantees for a large family of loss functions...

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