Seminars Sorted by Series

Non-constructive existence proofs, which establish the existence of objects without furnishing an efficient algorithm to produce examples, abound in mathematics. How hard is it, computationally, to find objects whose existence is guaranteed non...

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials P-n in n variables...

We consider the Glauber dynamics (also called Gibbs sampling) for sampling from a discrete distribution in high-dimensional space (e.g., selecting a uniformly random legal coloring or independent set in a given graph, or selecting a "typical" state...

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours.  The study of rainbow subgraphs goes back to the work of Euler on Latin squares in the 18th century.  Since then rainbow structures were the focus of...

For a fixed integer k > 1, the Boolean k-XOR problem consists of a system of linear equations mod 2 with each equation involving exactly k variables. We give an algorithm to strongly refute *semi-random* instances of the Boolean k-XOR problem on n...

The celebrated PCP theorem from the 90's shows that any mathematical proof can be encoded in such a way that its correctness can be verified locally by reading only a tiny number of bits from the encoding. This foundational result has had a...

What edge density of a graph guarantees that that it will contain a particular subgraph? Or one of a given family $\mathcal{F}$ of subgraphs? The celebrated Erdős--Stone--Simonovits Theorem characterizes the maximum edge density in $\mathcal{F}$...

In the max cut problem, we are given an n-vertex graph and we are asked what is the maximum fraction of edges "cut" by any partition of the vertices? This problem can be reformulated as an optimization problem over the cut polytope, which has...

In the Pandora's Box problem, the algorithm is provided with a number of boxes with unknown (stochastic) rewards contained inside them. The algorithm can open any box at some cost, discover the reward inside, and based on these observations can...

Many data analysis pipelines are adaptive: the choice of which analysis to run next depends on the outcome of previous analyses. Common examples include variable selection for regression problems and hyper-parameter optimization in large-scale...

Algorithms make predictions about people constantly.  The spread of such prediction systems has raised concerns that algorithms may exhibit unfair discrimination, especially against individuals from minority groups.  While it's easy to speculate on...

A random walk on expanders, despite its strong underlying correlations, poses extremely useful pseudorandom properties. The expander hitting property and the expander Chernoff are two such classic examples. That is, the AND function and certain...

Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants.  In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P...

Given i.i.d. samples drawn from an unknown distribution over a large domain [N], approximating several basic quantities, such as the distribution's support size and its Shannon Entropy, requires at least roughly (N / \log N) samples [Valiant and...

We consider the problem of computing a Gradient Descent solution of a continuously differentiable function f on a bounded convex domain, i.e., finding a "point where Gradient Descent terminates". Equivalently, this corresponds to computing a so...

What does the spectrum of a random matrix look like when we make no assumption whatsoever about the covariance pattern of its entries?  It may appear hopeless that anything useful can be said at this level of generality. Nonetheless, a widely used...

A locally testable code (LTC) is an error correcting code that admits a very efficient membership test. The tester reads a constant number of (randomly - but not necessarily uniformly - chosen) bits from a given word and rejects words with...

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly.  That is, we show that the value of the n-fold parallel repetition of the GHZ game is at most n^{-...

A Kakeya Set in (Z/N Z)^n is a set that contains a line in every direction.  It has been known for over a decade that such sets must be large when N is prime (or more generally over any finite field).  This goes back to Dvir's proof of the finite...

Constraint Satisfaction Problems (CSPs) are among the most well-studied problems in Computer Science, 3SAT being a prominent example.

Let $\Sigma$ be an alphabet and $P:\Sigma^k \rightarrow \{0,1\}$ be a fixed predicate. The assignments in $P^{-1}...

The ABNNR encoding is a classical encoding scheme that amplifies the distance of an error correcting code. The encoding takes an error correcting code with a small distance and constructs an error correcting code with distance approaching one, by...

Reproducibility is vital to ensuring scientific conclusions are reliable, but failures of reproducibility have been a major issue in nearly all scientific areas of study in recent decades. A key issue underlying the reproducibility crisis is the...

The degree mantra states that any non-zero univariate polynomial of degree at most d has at most d roots (counted with multiplicity). A generalization of this to the multivariate setting, proved by Dvir-Kopparty-Saraf-Sudan asserts that over any...

This talk will serve as an introduction to the random algebraic method. This method has its origins in the following problem: suppose the binomial random graph comes "close" to having some property of interest P, but fails to do so because of the...

We extend the classical theory of PAC learning in a way which allows to model a rich variety of practical learning tasks where the data satisfies special properties that ease the learning process. This is done by considering partial concepts...

I'll present a new algorithm to refute, that is, efficiently find certificates of unsatisfiability, for smoothed instances of k-SAT and other CSPs. Smoothed instances are produced by starting with a worst-case instance and flipping each literal in...

Understanding the complexity of the Minimum Circuit Size Problem (MCSP) is a longstanding mystery in theoretical computer science. Despite being a natural problem about circuits (given a Boolean function's truth table, determine the size of the...

As machine learning is widely deployed, it is increasingly important to ensure that predictors will perform well not only on average (across the entire population), but also on specific socially salient subgroups. In this talk, I will present...

Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in the area of Matching-Based Market Design.  The resurgence of this...

Proving a 2009 conjecture of Itai Benjamini, we show:  For any C, there is a > 0 such that for any simple random walk on an n-vertex graph G, the probability that the first Cn steps of the walk hit every vertex of G is at most exp[-an].  A first...

A nodal domain of a Laplacian eigenvector of a graph is a maximal connected component where it does not change sign.  Sparse random regular graphs have been proposed as discrete toy models of "quantum chaos", and it has accordingly been conjectured...

Blockchains that support a general contract layer (e.g., Ethereum) export the functionality of a general-purpose, ownerless, and open-access computer that can enforce property rights for digital data.  How is such functionality implemented?  Using a...

Since the late 19th century, mathematicians have realized the importance and generality of selection problems: given a collection of sets, select an element in each set, possibly in a ``nice” way.  Of particular importance in computer science is the...

Understanding the behavior of multi-player (multi-prover) games under parallel repetition is an important problem in theoretical computer science.

In a $k$-player game $G$, a referee chooses questions $(x^{1}, ..., x^{k})$ from a (publicly known)...

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas.  In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is...

It may seem quite obvious that graphs carry a lot of geometric structure.  Don't we learn in algorithm classes how to solve all-pairs-shortest-paths, minimum spanning trees etc.?  However, in this talk, I will try to impress on you the idea that...

A central topic in the theory of computation is derandomization: say we have an algorithm which flips coins to achieve some goal, and succeeds with high probability. Can we transform this algorithm into a deterministic procedure, while maintaining...

The notion of Schmidt rank/strength for a collection of m polynomials plays an important role in additive combinatorics, number theory and commutative algebra; high rank collections of polynomials are “psuedorandom”.  An arbitrary collection of...

Algorithms for understanding data generated from distributions over large discrete domains are of fundamental importance.  In this talk, we consider the sample complexity of *property testing algorithms* that seek to to distinguish whether or not an...

In interactive coding, Alice and Bob wish to compute some function f of their private inputs x and y. They do this by engaging in a non-adaptive (fixed speaking order, fixed length) protocol to jointly compute f(x,y). The goal is to do this in an...

Suppose we are given a random rank-r order-3 tensor---that is, an n-by-n-by-n array of numbers that is the sum of r random rank-1 terms---and our goal is to recover the individual rank-1 terms. In principle this decomposition task is possible when...

Many algorithms and heuristics that work well in practice have poor performance under the worst-case analysis, due to delicate pathological instances that one may never encounter. To bridge this theory-practice gap, Spielman and Teng introduced the...

In this talk, I'll discuss a recent result where we settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation:  The two-party communication, AND query, OR query...

In this talk, we show a strong XOR lemma for bounded-round two-player randomized communication.  For a function f:X×Y→{0,1}, the n-fold XOR function f^⊕n:X^n×Y^n→{0,1} maps n input pairs (x_1,...,x_n), (y_1,...,y_n) to the XOR of the n output bits f...

Sampling from high-dimensional, multimodal distributions is a computationally challenging and fundamental task.  This talk will focus on a family of random instances of such problems described by random quadratic potentials on the hypercube known as...

The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achieving arbitrarily high accuracy when given enough training data. We...