Seminars Sorted by Series

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

Boolean function analysis traditionally studies Boolean functions on the Boolean cube, using Fourier analysis on the group Z_2^n. Other domains of interest include the biased Boolean cube, other abelian groups, and Gaussian space. In all cases, the...

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the...

We prove that if every problem in NP has n^k-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier's search space has a witness for x that can be encoded with a circuit...

What is the probability that the number of triangles in the Erd\H{o}s-R\'enyi random graph with edge density $p$, is at least twice its mean? What is the typical structure of the graph conditioned on this rare event? For instance, when $p=o(1)$...

Polynomial optimization over hypercubes has important applications in combinatorial optimization. We develop a symmetry-reduction method that finds sums of squares certificates for non-negative symmetric polynomials over k-subset hypercubes that...

The EKR theorem, which is the cornerstone of extremal combinatorics, characterizes maximal intersecting families of sets. Its setting fixes a ground set of size n, and then studies the size and structure of intersecting families of subsets of fixed...

In their seminal paper, Bennett, Bernstein, Brassard and Vazirani [SICOMP, 1997] showed that relative to an oracle, quantum algorithms are unable to solve NP-complete problems in sub-exponential time (i.e., that Grover's search is optimal in this...

We will describe a recently discovered connection between private information retrieval and secret sharing, and a new secret-sharing scheme for general access structures that breaks a long-conjectured exponential barrier.

Based on joint work with...

Edit distance is a widely used measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a...

For a family of graphs F, a graph G is F-universal if G contains every graph in F as a (not necessarily induced) subgraph. A natural candidate to serve as universal graph G is the random graph G(n,p). In this case, we want to find an optimal p for...

Let X be the infinite graph partially pictured below, the "free product graph" C_4 * C_4 * C_4. Let FinQuo(X) be the set of all finite graphs G that covered by X (i.e., that 'locally resemble' X; i.e., that consist of C_4's joined 3-to-a-vertex). A...

The Erdos-Rado sunflower conjecture is one of the tantalizing open problems in combinatorics. In my talk, I will describe several attempts on how to get improved bounds for it. These will lead to surprising connections with several other...

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which allows a classical string to serve as a commitment to a...

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which allows a classical string to serve as a commitment to a...

Chernoff-type bounds study concentration of sums of independent random variables and are extremely useful in various settings. In many settings, the random variables may not be completely independent but only have limited independence. One such...

In this talk, I will give an overview on how PCPs, combined with cryptographic tools, are used to generate succinct and efficiently verifiable proofs for the correctness of computations. I will focus on constructing (computationally sound) *succinct...

Randomness dispersers are an important tool in the theory of pseudorandomness, with numerous applications. In this talk, we will consider one-bit strong dispersers and show their connection to erasure list-decodable codes and Ramsey graphs.

The...

A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit...

A matroid is an abstract combinatorial object which generalizes the notions of spanning trees, and linearly independent sets of vectors. I will talk about an efficient algorithm based on the Markov Chain Monte Carlo technique to approximately count...