Seminars Sorted by Series

A perfect matching in a $k$-uniform hypergraph $H= (V, E)$ on $n$ vertices is a set of $n/k$ disjoint edges of $H$, while a fractional perfect matching in $H$ is a function $w:E \to [0,1]$ such that for each $v \in V$ we have $\sum_{e \ni v}w(e) = 1...

The famous theorem of Szemerédi says that for any natural number k and any a > 0 there exists n such that if N >= n then any subset A of the set [N] ={1,2,...,N} of size |A| >= a N contains an arithmetic progression of length k. We consider the...

In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial...

The classical Dvoretzky theorem asserts that for every integer k>1 and every target distortion D>1 there exists an integer n=n(k,D) such that any n-dimensional normed space contains a subspace of dimension k that embeds into Hilbert space with...

A ``tournament'' is a digraph obtained from a complete graph by directing its edges, and ``colouring'' a tournament means partitioning its vertex set into acyclic subsets (``acyclic'' means the subdigraph induced on the subset has no directed cycles...

A popular practical method of obtaining a good estimate of the error rate of a learning algorithm is k-fold cross-validation. Here, the set of examples is first partitioned into k equal-sized folds. Each fold acts as a test set for evaluating the...

This paper revisits the construction of Universally One-Way Hash Functions (UOWHFs) from any one-way function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs which also obtains better efficiency and security. The construction...

The Johnson-Lindenstrauss lemma states that for any n points in Euclidean space and error parameter 0

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