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.