|
Simulating Independence: New Constructions of Condensers, Ramsey
Graphs, Dispersers, and Extractors
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson
Abstract
A distribution X over binary strings of length n has min-entropy k
if every string has probability at most 2-k in X. X is called a
r-source if its rate k/n is at least r.
We give the following new explicit constructions (namely, poly(n)-time
computable functions) of *deterministic* extractors, dispersers and
related objects. All work for any fixed rate r>0. No previous
explicit construction was known for either of these, for any r<1/2.
The first two constitute major progress to very long-standing open problems.
Bipartite Ramsey: A function BR: ({0,1}n )2 ---> {0,1},
such that for any two independent delta-sources X,Y
we have BR(X,Y) = {0,1}.
This implies a new explicit construction of 2N-vertex
bipartite graphs where no induced Nr by Nr
subgraph is complete or empty.
Multiple source extraction: a function
EXT: ({0,1}n )3 --> {0,1}, such that for any three
independent r-sources X,Y,Z we have that
EXT(X,Y,Z) is (o(1)-close to being) an unbiased random bit.
Constant seed condenser: a function
CON: {0,1}n --> ({0,1}m )c,
such that for any r-source X, one of the c output
distributions CON(X)i, is a 0.9-source over {0,1}m.
Here c is a constant depending only on r.
This result was also independently obtained by Ran Raz.
Subspace Ramsey: a function AR: {0,1}n --> {0,1},
such that for any affine-delta-source (i.e., a uniform
distribution over an affine subspace of dimension at
least r n) X we have AR(X)= {0,1}
The constructions are quite involved and use as building blocks
other new and known gadgets. But we can point out two important
themes which recur in these constructions. One is that gadgets which
were designed to work with independent inputs, sometimes perform
well enough with correlated, high entropy inputs. The second is
using the input to (introspectively) find high entropy regions within
itself.
Versions
|