Seminars Sorted by Series

Interactive proofs have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity...

We show that the bipartite perfect matching problem is in $\textrm{quasi-}\textsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such...

We study the two-party communication complexity of the geometric problem of finding an approximate Brouwer fixed-point of a composition of two Lipschitz functions $g \circ f$, where Alice knows $f$ and Bob knows $g$. We prove an essentially tight...

The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools. In the first talk we outline the algorithm and state the core group theoretic and algorithmic ingredients. Some of...

Finding cliques in random graphs and the related planted variant where one wants to recover an added clique of size $k$ added to a random $G(n, 1/2)$ graph, have been extensively studied questions in algorithm design. Despite intense effort, state...

The last few years have seen substantial progress on the question of proving lower bounds for homogeneous depth-4 arithmetic circuits. Even though these results seem to come close to resolving the VP vs VNP question, it seems likely that the...

Tensor decompositions have been the key algorithmic components in provable learning of a wide range of hidden variable models such as topic models, Gaussian mixture models, independent component analysis, dictionary learning. Despite its success...

What is the distribution of the number of triangles in the random graph $G(n, 1/2)$? It was known for a long time that this distribution obeys a central limit theorem: from the point of view of large intervals (~ standard-deviation length), the...

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \\geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a...

Random constraint satisfaction problems encode many interesting questions in random graphs such as the chromatic and independence numbers. Ideas from statistical physics provide a detailed description of phase transitions and properties of these...

The determinant of an $n\times n$ matrix is an invariant polynomial of degree $n$ that is invariant under left and right multiplication with matrices in ${\rm SL}_n$. It generates in the sense that every other invariant polynomial is a polynomial...

Monotonicity testing has been a touchstone problem in property testing for more than fifteen years, with many exciting recent developments in just the past few years. When specialized to Boolean-valued functions over $\{0,1\}^n$, we are interested...

For a constant $\epsilon$, we prove a $\mathrm{poly}(N)$ lower bound on the communication complexity of $\epsilon$-Nash equilibrium in two-player $N \times N$ games. For $n$-player binary-action games we prove an $\exp(n)$ lower bound for the...

Let $G$ be a compact group and let $f_{ij}\in L_2(G)$ be bandlimited functions. We define the Non-Unique Games (NUG) problem as finding $g_1\ldots,g_n\in G$ to minimize $\sum_{i,j=1}^n f_{ij}(g_i g_j^{-1})$. We devise a relaxation of the NUG problem...

I will review some of the recent techniques we've used in our study of natural algorithms. These include Dirichlet series for matrix products, mean-field approximations in opinion dynamics, graph sequence grammars, and tools for renormalizing...

The random planted 3-coloring model generates a 3-colorable graph $G$ by first generating a random host graph $H$ of average degree $d$, and then planting in it a random 3-coloring (by giving each vertex a random color and dropping the monochromatic...

The stochastic block model (SBM) is a random graph model with planted clusters. It has been popular to model unsupervised learning problems, inhomogeneous random graphs and to study statistical versus computational tradeoffs. This talk overviews the...

Consider a set of $n$ points in $\mathbb R^d$. The classical theorem of Sylvester-Gallai says that, if the points are not all collinear then there must be a line through exactly two of the points. Let us call such a line an "ordinary line". In a...

The motivating question for this talk is: What does a sparse Erdős–Rényi random graph, conditioned to have twice the number of triangles than the expected number, typically look like? Motivated by this question, In 2014, Chatterjee and Dembo...

The "cap set problem" asks for the size of the largest subset $S$ of the vector space $\mathbb F_3^n$ containing no three elements summing to 0. Progress on this problem was slow for many years, until the spring of 2016, when a very short argument...

An active learning algorithm for a classification problem has access to many unlabelled samples. The algorithm asks for the labels of a small number of samples, carefully chosen, such that that it can leverage this information to correctly label...

In this talk, I will discuss our recent efforts to formalize a particular notion of “fairness” in online decision making problems, and study its costs on the achievable learning rate of the algorithm. Our focus for most of the talk will be on the...

Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with $n$ variables and $m$ clauses, there is a value of $m = \Omega(n)$ beyond which the CSP will be unsatisfiable...

I will show a new efficient approximate nearest neighbor search (ANN) algorithm over an arbitrary high-dimensional *symmetric* norm. Traditionally, the ANN problem in high dimensions has been studied over the $\ell_1$ and $\ell_2$ distances with a...

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We present new results relating the complexity of various approximation...

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant...

The computational complexity of finding Nash Equilibria in games has received much attention over the past two decades due to its theoretical and philosophical significance. This talk will be centered around the connection between this problem and...

We introduce a new approach for approximately counting in bounded degree systems with higher-order constraints. Our main result is an algorithm to approximately count the number of solutions to a CNF formula where the degree is exponential in the...

Recently, a certain "monotone" version of the constraint satisfaction problem has proved an extremely useful tool for attacking problems in circuit, communication, and proof complexity theory. In this talk we discuss this version of the constraint...

We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. As a...

This talk will survey some recent advances in research on program obfuscation, an area of theoretical cryptography that has seen unprecedented levels of activity over the last four years. We will cover material starting from the basics, and no prior...

We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments...

One of the great mysteries in computational condensed matter physics is the remarkable practical success of the Density Matrix Renormalization Group (DMRG) algorithm, since its invention a quarter century ago, for finding low energy states of 1D...

One of the great mysteries in computational condensed matter physics is the remarkable practical success of the Density Matrix Renormalization Group (DMRG) algorithm, since its invention a quarter century ago, for finding low energy states of 1D...

This paper proves the first super-logarithmic lower bounds on the cell-probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.We introduce a new method for proving...

Arithmetic complexity is considered (for many good reasons) simpler to understand than Boolean complexity. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite...

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. For any constant $\delta > 0$, we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta}...

A weight-$t$ halfspace is a Boolean function $f(x)=\mathrm{sign}(w_1 x_1 + \cdots + w_n x_n - \theta)$ where each $w_i$ is an integer in $\{-t,\dots,t\}.$ We give an explicit pseudorandom generator that $\delta$-fools any intersection of $k$ weight-...

The language edit distance is a significant generalization of two basic problems in computer science: parsing and string edit distance computation. Given any context free grammar, it computes the minimum number of insertions, deletions and...

A theme that cuts across many domains of computer science and mathematics is to find simple representations of complex mathematical objects such as graphs, functions, or distributions on data. These representations need to capture how the object...

We show that there exist binary locally testable codes (for all rates) and locally correctable codes (for low rates) with rate and distance approaching the Gilbert-Varshamov bound (which is the best rate-distance tradeoff known for general binary...

A martingale is a sequence of random variables that maintain their future expected value conditioned on the past. A $[0,1]$-bounded martingale is said to polarize if it converges in the limit to either $0$ or $1$ with probability $1$. A martingale...

It is classically understood how to learn the parameters of a Gaussian even in high dimensions from independent samples. However, estimators like the sample mean are very fragile to noise. In particular, a single corrupted sample can arbitrarily...

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in polylogarithmic time on quasi-polynomially many processors. The result is obtained by a derandomization of...

I will show an explicit construction of a binary error correcting code with relative distance $\frac{1-\epsilon}{2}$ and relative rate $\epsilon^{2+o(1)}$. This comes close to the Gilbert-Varshamov bound that shows such codes with rate $\epsilon^2$...

An error-correcting code is called locally repairable if any coordinate of a codeword can be recovered by accessing only few other coordinates. For locally repairable codes over small alphabets (such as binary), the optimal trade-off between...

The Random Fourier Features (RFF) method (Rahimi, Recht, NIPS 2007) is one of the most practically successful techniques for accelerating computationally expensive nonlinear kernel learning methods. By quickly computing a low-rank approximation for...

The hypergraph regularity lemma — the extension of Szemeredi's graph regularity lemma to the setting of k-graphs — is one of the most celebrated combinatorial results obtained in the past decade. By now there are various (very different) proofs of...