## Local Correlation Breakers
and Applications to Mergers and Multi-Source Extractors

by Gil Cohen

#### Oded's comments

This is quite a tour de force, at least in the sense that you
need force to remain on the tour. But once the LCB is obtained,
it is relatively easier to get the claimed applications
(provided you master the literature).
In any case, the application to three-source extractors is
highlighted due to the fact that the third source need only have
a tiny amount of min-entropy (i.e., double-logarithmic amount).
Reducing the min-entropy of the third source farther seems one way
to obtain an explicit two-source extractor for any constant min-entropy rate.

#### The original abstract

We introduce and construct a pseudo-random object which we call a local
correlation breaker (LCB). This is an algorithm that gets as input a
sequence of (possibly correlated) random variables and an independent weak
source of randomness. The output of the LCB is a sequence of random
variables with the following property. If the i'th input random variable is
uniform then the i'th output variable is uniform even if a bounded number
of any other output variables are given. That is, an LCB uses the
weak-source to "break" local correlations between random variables.

Based on LCBs we obtain improved constructions of mergers with weak-seeds
and multi-source extractors. In particular, we construct a 3-source
extractor for entropies delta*n, O(log n) and O(loglog n), for any constant
delta. We further construct a 7-source extractor for poly-logarithmic
entropy.

Back to
list of Oded's choices.