We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of $r$ (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of $r$ random variables with the following property. If the $i$'th input random variable is uniform then the $i$'th output variable is uniform even given a bounded number of any other output variables. That is, an LCB uses the weak-source to "break" local correlations between random variables. Using our construction of LCBs, we obtain the following results:
* We construct a three-source extractor where one of the sources is only assumed to have a double-logarithmic entropy. More precisely, for any integer $n$ and constant $\delta>0$, we construct a three-source extractor for entropies $\delta n$, $O(\log{n})$ and $O(\log\log{n})$. This result improves the three-source extractor of Raz [STOC'05] and is incomparable with the recent three-source extractor by Li [FOCS'15]. As the third source is required to have tantalizingly low entropy, we hope that further ideas can be used to eliminate the need for this source altogether.
* We construct a merger with weak-seeds that merges $r$ random variables using an independent $(n,k)$-weak-source with $k = \widetilde{O}(r) \cdot \log\log{n}$. A previous construction by Barak, Rao, Shaltiel, and Wigderson [Ann. Math'12] assumes $k \ge \Omega(r^2) + \polylog(n)$.
* We introduce the notion of a two-source non-malleable extractor. This is a relaxation of a non-malleable extractor, introduced by Dodis and Wichs [STOC'09] where two weak-sources, rather than one, are given. We construct a two-source non-malleable extractor for entropy $O(\log^2{n})$ with a logarithmic seed length.
Besides a revision of the introduction, this version includes an application of LCBs to the construction of two-source non-malleable extractors with logarithmic seed length.
We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of $r$ (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of $r$ random variables with the following property. If the $i$'th input random variable is uniform then the $i$'th output variable is uniform even given a bounded number of any other output variables. That is, an LCB uses the weak-source to "break" local correlations between random variables. Using our construction of LCBs, we obtain the following results:
* We construct a three-source extractor where one of the sources is only assumed to have a double-logarithmic entropy. More precisely, for any integer $n$ and constant $\delta>0$, we construct a three-source extractor for entropies $\delta n$, $O(\log{n})$ and $O(\log\log{n})$. As the third source is required to have tantalizingly low entropy, we hope that further ideas can be used to eliminate the need for this source altogether.
* We construct a merger with weak-seeds that merges $r$ random variables using an independent $(n,k)$-weak-source with $k = \widetilde{O}(r) \cdot \log\log{n}$. A previous construction by Barak et al [Ann. Math'12] assumes $k \ge \Omega(r^2) + \polylog(n)$.
