Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-038 | 7th July 2015 13:08

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

RSS-Feed




Revision #1
Authors: Gil Cohen
Accepted on: 7th July 2015 13:08
Downloads: 730
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Paper:

TR15-038 | 11th March 2015 20:44

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers





TR15-038
Authors: Gil Cohen
Publication: 11th March 2015 21:45
Downloads: 729
Keywords: 


Abstract:

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)$.



ISSN 1433-8092 | Imprint