ECCC-Report TR15-038https://eccc.weizmann.ac.il/report/2015/038Comments and Revisions published for TR15-038en-usTue, 07 Jul 2015 13:08:35 +0300
Revision 1
| Local Correlation Breakers and Applications to Three-Source Extractors and Mergers |
Gil Cohen
https://eccc.weizmann.ac.il/report/2015/038#revision1We 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.
Tue, 07 Jul 2015 13:08:35 +0300https://eccc.weizmann.ac.il/report/2015/038#revision1
Paper TR15-038
| Local Correlation Breakers and Applications to Three-Source Extractors and Mergers |
Gil Cohen
https://eccc.weizmann.ac.il/report/2015/038We 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)$.
Wed, 11 Mar 2015 21:45:22 +0200https://eccc.weizmann.ac.il/report/2015/038