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 TR19-173 | 20th June 2020 00:42

Extractor Lower Bounds, Revisited

RSS-Feed




Revision #1
Authors: Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz
Accepted on: 20th June 2020 00:42
Downloads: 554
Keywords: 


Abstract:

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a ``change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input sources with sufficient min-entropy, a somewhere extractor only requires that there exists a seed whose output bias is small. More generally, we study what we call probable extractors, which on input a source with sufficient min-entropy guarantee that a large enough fraction of seeds have small enough associated output bias. Such extractors have played a key role in many constructions of pseudorandom objects, though they are often defined implicitly and have not been studied extensively.

Prior known techniques fail to yield good seed length lower bounds when applied to the variants above. Our novel approach yields significantly improved lower bounds for somewhere and probable extractors. To complement this, we construct a somewhere extractor that implies our lower bound for such functions is tight in the high min-entropy regime. Surprisingly, this means that a random function is far from an optimal somewhere extractor in this regime. The techniques that we develop also yield an alternative, simpler proof of the celebrated optimal lower bound for strong extractors originally due to Radhakrishnan and Ta-Shma (SIAM J. Discrete Math., 2000).



Changes to previous version:

Implemented reviewer's comments.


Paper:

TR19-173 | 28th November 2019 11:25

Extractor Lower Bounds, Revisited


Abstract:

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a ``change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input sources with sufficient min-entropy, a somewhere extractor only requires that there exists a seed whose output bias is small. More generally, we study what we call probable extractors, which on input a source with sufficient min-entropy guarantee that a large enough fraction of seeds have small enough associated output bias. Such extractors have played a key role in many constructions of pseudorandom objects, though they are often defined implicitly and have not been studied extensively.

Prior known techniques fail to yield good seed length lower bounds when applied to the variants above. Our novel approach yields significantly improved lower bounds for somewhere and probable extractors. To complement this, we construct a somewhere extractor that implies our lower bound for such functions is tight in the high min-entropy regime. Surprisingly, this means that a random function is far from an optimal somewhere extractor in this regime. The techniques that we develop also yield an alternative, simpler proof of the celebrated optimal lower bound for strong extractors originally due to Radhakrishnan and Ta-Shma (SIAM J. Discrete Math., 2000).



ISSN 1433-8092 | Imprint