Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-052 | 7th April 2016 16:41

Making the Most of Advice: New Correlation Breakers and Their Applications


Authors: Gil Cohen
Publication: 8th April 2016 11:01
Downloads: 1450


A typical obstacle one faces when constructing pseudorandom objects is undesired correlations between random variables. Identifying this obstacle and constructing certain types of "correlation breakers" was central for recent exciting advances in the construction of multi-source and non-malleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These are algorithms that break the correlation a "bad" random variable $Y'$ has with a "good" random variable $Y$ using an "advice" - a fixed string $\alpha$ that is associated with $Y$ which is guaranteed to be distinct from the corresponding string $\alpha'$ associated with $Y'$. Prior to this work, explicit constructions of correlation breakers with advice require the entropy of the involved random variables to depend linearly on the advice length.

In this work, building on independence-preserving mergers, a pseudorandom primitive that was recently introduced by Cohen and Schulman, we devise a new construction of correlation breakers with advice that has optimal, logarithmic, dependence on the advice length. This enables us to obtain the following results.

* We construct an extractor for $5$ independent $n$-bit sources with min-entropy $(\log{n})^{1+o(1)}$. This result puts us tantalizingly close to the goal of constructing extractors for $2$ sources with min-entropy $O(\log{n})$, which would have exciting implications to Ramsey theory.

* We construct non-malleable extractors with error guarantee $\epsilon$ for $n$-bit sources, with seed length $d = O(\log{n}) + (\log(1/\epsilon))^{1+o(1)}$ for any min-entropy $k = \Omega(d)$. Prior to this work, all constructions require either very high min-entropy or otherwise have seed length $\omega(\log{n})$ for any $\epsilon$. Further, our extractor has near-optimal output length. Prior constructions that achieve comparable output length work only for very high min-entropy $k \approx n/2$.

* By instantiating the Dodis-Wichs framework with our non-malleable extractor, we obtain near-optimal privacy amplification protocols against active adversaries, improving upon all (incomparable) known protocols.

ISSN 1433-8092 | Imprint