Seminars Sorted by Series

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

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