Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-037 | 8th March 2010 15:03

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors



We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a
distribution $X$ on binary strings of length $n$ is a
$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$
to any string of length $n$. For every $\delta>0$ we construct the
following poly($n$)-time computable functions:

1) (2-source disperser:) $D:(\{0,1\}^n)^2 \rightarrow \{0,1\}$ such that for any two independent $\delta$-sources
$X_1,X_2$ we have that the support of $D(X_1,X_2)$ is $\{0,1\}$.

2) (Bipartite Ramsey graph:) Let $N=2^n$. A corollary is that the function $D$ is a 2-coloring of the edges of $K_{N,N}$ (the complete
bipartite graph over two sets of $N$ vertices) such that any induced subgraph of size $N^{\delta}$ by
$N^{\delta}$ is not monochromatic.

(3) (3-source extractor:) $E:(\{0,1\}^n)^3 \rightarrow \{0,1\}$ such that for any three independent
$\delta$-sources $X_1,X_2,X_3$ we have that $E(X_1,X_2,X_3)$ is $o(1)$-close to being an unbiased random bit.

No previous explicit construction was known for either of these for any $\delta<1/2$, and these results
constitute significant progress to long-standing open problems.

A component in these results is a new construction of condensers
that may be of independent interest: This is a function $C:\{0,1\}^n
\rightarrow (\{0,1\}^{n/c})^d$ (where $c$ and $d$ are constants that
depend only on $\delta$) such that for every $\delta$-source $X$
one of the output blocks of $C(X)$ is (exponentially close to) a
$0.9$-source. (This result was obtained independently by Ran Raz).

The constructions are quite involved and use as building blocks
other new and known objects. A recurring theme in these
constructions is that objects which were designed to work with
independent inputs, sometimes perform well enough with correlated,
high entropy inputs.

Preliminary version of this paper appeared in STOC 2005.

ISSN 1433-8092 | Imprint