Seminars Sorted by Series

"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly. Estimating the value of such games (i.e., winning probability under optimal play by the strategic player) is an...

Establishing inequalities among graph densities is a central pursuit in extremal graph theory. One way to certify the nonnegativity of a graph density expression is to write it as a sum of squares or as a rational sum of squares. In this talk, we...

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