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.

Lemma 11.6 in the original version of this paper asserts that the bitwise XOR of $m$ independent $n$-bit random variables, each $\epsilon$-close to a $k$-source, is $\epsilon^m$-close to a $k$-source. This lemma generalizes an assertion due to Barak, Impagliazzo and Wigderson (SICOMP 2006) who considered the uniform case (namely, $k=n$).

Proving Lemma 11.6 was given in a problem set in a course taught by Amnon Ta-Shma. While most students successfully proved the lemma, one student, Dori Medini, struggled with the problem. When referred to the paper, Dori pointed at a flaw in the proof (and in the proof given by all other students...).

In this revision we give a proof of a slightly weaker lemma, showing that the XOR as above is $(2\epsilon)^m$-close to a $k-2$ source. This slight deterioration in the closeness parameter and in the min-entropy is insignificant for the purpose of this paper. In particular, the $5$-source extractor constructed in this paper retains its original (asymptotic) parameters.

Fixing the flaw in our proof was done jointly with Alon Frydberg. I thank Dori and Alon for raising the issue and assisting in fixing the flawed lemma, respectively.

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.