Seminars Sorted by Series

For a graph $G$, let $t(G)$ (resp. $b(G)$) denote the maximum size of a triangle-free (resp. bipartite) subgraph of $G$. Of course $t(G) \geq b(G)$ for any $G$, and a classic result of Mantel from 1907 (the first case of Turan’s Theorem) says $t(K_n...

A long-standing line of work in economic theory has studied models by which a group of people in a social network, each holding a numerical opinion, can arrive at a shared opinion through repeated averaging with their neighbors in the network...

We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in log(1/epsilon), where epsilon > 0...

In 1970s Paul Erdos asked the following question: Consider all the boolean strings of length n. Assume that one has chosen a subset S of the strings such that no two chosen strings are different in precisely n/4 (or its closest even integer)...

We show that there exists an $N$-point subset of $L_1$ such that for every $D > 1$, embedding it into $\ell^d_1$ with distortion $D$ requires dimension $d$ at least $N^{\Omega(1/D^2)}$, and that for every $\epsilon > 0$ there exists an $N$-point...

We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4-epsilon) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing the...

Given two monotone polynomials f,g, their unifier is a pair of monotone polynomials u,v such that f=cu+v and g=u+cv, for some c>0. The problem I will discuss is: can we have monotone polynomials f,g which have a unifier, they can be computed by a...

In the file maintenance problem, n integer items from the set {1,....,r} are to be stored in an array of size m>=n . The items are presented sequentially in an arbitrary order and must be stored in the array in sorted order (but not necessarily in...

Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume estimation of convex...

To examine the limiting behavior of graph sequences, many discrete methods meet their continuous counterparts, leading to numerous theoretical and applicable advancements. For dense graph sequences, the graph limits have recently been well developed...

We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of x . Our main focus...

Partitioning the vertices of a graph into two (roughly) equal parts to minimize the weight of edges cut is a fundamental optimization problem, arising in diverse applications. Despite intense research, there remains a huge gap in our understanding...

For a {0,1}-valued matrix M let CC(M) denote he deterministic communication complexity of the boolean function associated with M. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC(M) <= log^c(rank(M)) for some absolute constant c where rank(M) denotes the rank of M over the field of real numbers. We show that CC(M) <= c rank(M)/logrank(M) for some absolute constant c, assuming a well-known conjecture from additive combinatorics, known as the Polynomial Freiman-Ruzsa (PFR) conjecture. Our proof is based on the study of the "approximate duality conjecture" which was recently suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, and this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995]. This is joint work with Eli Ben-Sasson and Shachar Lovett.

Complexity theory, with some notable exceptions, typically studies the complexity of computing a function h(x) of a *given* input x. We advocate the study of the complexity of generating -- or sampling -- the output distribution h(x) for random x...

The braid group on n strands may be viewed as an infinite analog of the symmetric group on n elements with additional topological phenomena. It appears in several areas of mathematics, physics and computer sciences, including knot theory, algebraic...

In joint work with Paul Valiant, we consider the tasks of estimating a broad class of statistical properties, which includes support size, entropy, and various distance metrics between pairs of distributions. Our estimators are the first proposed...

The problem of combinatorial auctions is one of the basic questions in algorithmic mechanism design: how can we allocate/sell m items to n agents with private valuations of different combinations of items, so that the agents are motivated to reveal...

We study a new type of proof system, where an unbounded prover and a polynomial time verifier interact, on inputs a string $x$ and a function $f$, so that the Verifier may learn $f(x)$. The novelty of our setting is that there no longer are ``good"...

The goal of the Balanced Separator problem is to find a balanced cut in a given graph G(V,E), while minimizing the number of edges that cross the cut. It is a fundamental problem with applications in clustering, image segmentation, community...

Shannon's notion of entropy measures the amount of "randomness" in a process. However, to an algorithm with bounded resources, the amount of randomness can appear to be very different from the Shannon entropy. Indeed, various measures of...

It is a long-standing problem to lower bound the performance of randomized greedy algorithms for maximum matching. Aronson, Dyer, Frieze and Suen in1995 studied the modified randomized greedy (MRG) algorithm and proved that it approximates the...

Gowers' uniformity norms are defined by average of a function over specific sets of linear forms. We study norms that are similarly defined by a system of linear forms. We prove that for bounded complex functions over $F_p^n$, each such norm is...

The security of several cryptosystems is based on our apparent inability to solve the following computational problem: given as input a basis B for a lattice and a target vector t , find the lattice point closest to t. This problem, referred to as...

This talk will be a partial survey of the first questions in the complexity theory of geometric topology problems. What is the complexity, or what are known complexity bounds, for distinguishing n-manifolds for various n? For distinguishing knots...

If $x$, $y$, and $z$ are random vectors, what is the expectation of the product of their inner products, $\langle x,y \rangle$, $\langle y, z \rangle$, $\langle z, x\rangle$? If $U$ and $V$ are random unitary matrices, what is the expected trace of...

A matrix A naturally defines a quadratic form x^tAy. If A is of rank <=r, then the rank<=r decomposition of A corresponds naturally to a size ~2nr circuit for computing the quadratic form. It is clear how to perform "white box" polynomial identity testing for such circuits, and the motivating question for this work is to explore black-box identity testing. The probabilistic method shows that there is a size ~2nr hitting set for such polynomials. In this work we match this bound (over large fields), which is optimal up to constant factors. Further, we explore how A can be reconstructed from the evaluations of the quadratic form. Similar probabilistic constructions show that there exist ~4nr evaluations which determine any such matrix A. Again, we match this bound (over large fields) with an explicit construction, and furthermore give a polynomial-time algorithm to reconstruct A from such evaluations. More generally, we show an efficient reduction from (exact) low-rank matrix reconstruction to (exact) sparse recovery. This reduction is novel in the compressed-sensing realm as it is field independent and unrelated to convex optimization. Finally, using matrices as a base case we also derive a quasi-polynomial hitting set for higher-order tensors. Joint work with Michael Forbes.

We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers...

We study algorithms for combinatorial market design problems, where a collection of objects are priced and sold to potential buyers subject to equilibrium constraints. We introduce the notion of a combinatorial Walrasian equilibrium (CWE) as a...

Holant Problems are a broad framework to describe counting problems. The framework generalizes counting Constraint Satisfaction Problems and partition functions of Graph Homomorphisms. We prove a complexity dichotomy theorem for Holant problems over...

Polynomial Identity Testing (PIT) is the problem of identifying whether a given algebraic circuit computes the identically zero polynomial. It is well-known that this problem can be solved with small error probability by testing whether the circuit...

In this talk we will discuss information complexity -- a measure of the amount of information Alice and Bob need to exchange to solve a problem over distributed inputs. We will present an information-theoretically optimal protocol for computing the...

For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication)...

For a set of polynomials F, we define their bilinear complexity as the smallest k so that F lies in an ideal generated by k bilinear polynomials. The main open problem is to estimate the bilinear complexity of the single polynomial $\sum_{i,j}x_i^2...

In small dimension a random geometric graph behaves very differently from a standard Erdös-Rényi random graph. On the other hand, when the dimension tends to infinity (with the number of vertices being fixed) both models coincide. In this talk we...

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that such an extractor exists for two sources on n bits with min-entropy k >= 2 log n. On the other hand, explicit constructions are...

I will describe some recent results and problems regarding influence of sets of variables on Boolean functions: In 1989 Benny Chor conjectured that a balanced Boolean function with n variables has a subset S of size 0.4n with influence (1-c^n) where...

With the notion of interaction with oracles as a unifying theme of much of my dissertation work, I discuss novel models and results for property testing and computational learning, with the use of Fourier analytic and probabilistic methods. One...

Polar codes have recently emerged as a new class of low-complexity codes achieving Shannon capacity. This talk introduces polar codes with emphasis on the probabilistic phenomenon underlying the code construction. New results and connections to...

Since the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there has been a lot of effort by many researchers to extend the theory to hypergraphs. I will present some of this history, and then...

We discuss three areas of algorithmic game theory that have grappled with intractability. The first is the complexity of computing game-theoretic equilibria, like Nash equilibria. There is an urgent need for new ideas on this topic, to enable...

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural...

Locally decodable codes (LDCs) are error-correcting codes that allow for highly-efficient recovery of "pieces" of information even after arbitrary corruption of a codeword. Locally testable codes (LTCs) are those that allow for highly-efficient...

A trusted source of independent and uniform random bits is a basic resource in many computational tasks, such as cryptography, game theoretic protocols, algorithms and physical simulations. Implementing such a source presents an immediate challenge...