Seminars Sorted by Series

The Johnson-Lindenstrauss lemma (also known as Random Projections) states that any set of n points in Euclidian space can be embedded almost isometrically into another Euclidian space of dimension O(log(n)). The talk will focus on the efficiency of...

Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree...

The INDEX problem is one of a handful of fundamental problems in communication complexity: Alice has an n-bit string x, Bob has an index k in [n], and the players wish to determine the k-th bit of x. It is easy to show that the problem is "hard"...

We prove completeness results for certain class of functions which have implications for automatic proving of universally-composable security theorems for ideal and real functionalities composed of if-then-else programs with (uniform) random number...

Property testing considers the following general question: how many queries to some combinatorial object (e.g., a boolean function or a graph) do we need to determine whether the object has some property P or whether it is "far" from having the...

We show a (3/2-\epsilon)-approximation algorithm for the graphical traveling salesman problem where the goal is to find a shortest tour in an unweighted graph G. This is a special case of the metric traveling salesman problem when the underlying...

It is well-known that any Boolean function f:{-1,+1}^n \to {-1,+1} can be written uniquely as a polynomial f(x) = \sum_{S subset [n]} f_s \prod_{i in S} x_i. The collection of coefficients (f_S's) this expression are referred to (with good reason)...

Consider an optimization problem with n binary variables and d+1 linear objective functions. Each valid solution x in {0,1}^n gives rise to an objective vector in R^{d+1}, and one often wants to enumerate the Pareto optima among these. In the worst...

We prove a complexity dichotomy theorem for all non-negatively weighted counting Constraint Satisfaction Problems (#CSP). This caps a long series of important results on counting problems including unweighted and weighted graph homomorphisms and the...

Recursive Majority-of-three (3-Maj) is a deceptively simple problem in the study of randomized decision tree complexity. The precise complexity of this problem is unknown, while that of the similarly defined Recursive NAND tree is completely...

A "sparsifier" of a graph is a weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of (1 +/- eps). Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging...

In a joint work with Tsuyoshi Ito we have constructed a fingerprinting scheme (i.e., hashing) that leaks significantly less than log(1/epsilon) bits about the preimage, where epsilon is the error ("collision") probability. It is easy to see that...

A k-modal probability distribution over the domain {1,...,N} is one whose histogram has at most k "peaks" and "valleys". Such distributions are a natural generalization of the well-studied class of monotone increasing (or monotone decreasing)...

More than twenty years ago, Manickam, Miklos, and Singhi conjectured that for any integers $n \geq 4k$, every set of $n$ real numbers with nonnegative sum has at least $\binom{n-1}{k-1}$ $k$-element subsets whose sum is also nonnegative.

In this...

In settings of incomplete information, we put forward (1) a very conservative ---indeed, purely set-theoretic--- model of the beliefs (including totally wrong ones) that each player may have about the payoff types of his opponents, and (2) a new and...

Proving superpolylogarithmic lower bounds for dynamic data structures has remained an open problem despite years of research. Recently, Patrascu proposed an exciting new approach for breaking this barrier via a two player communication model in...

A pseudo-random graph is a graph G resembling a typical random graph of the same edge density. Pseudo-random graphs are expected naturally to share many properties of their random counterparts. In particular, many of their enumerative properties...

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