TR10-037 Authors: Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

Publication: 8th March 2010 15:03

Downloads: 1775

Keywords:

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.