2011-2012 Seminars

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

This is a survey talk about different attempts to deal with the very troubling phenomena of independence in Set Theory.

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

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. Many hardness reductions and constructions of integrality gap instances use the long code as a core gadget. However, this...

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

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. Many hardness reductions and constructions of integrality gap instances use the long code as a core gadget. However, this...

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

The notion of exactly (or approximately) representing certain combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are...

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

The notion of exactly (or approximately) representing certain combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are...