ECCC-Report TR19-173https://eccc.weizmann.ac.il/report/2019/173Comments and Revisions published for TR19-173en-usSat, 20 Jun 2020 00:42:21 +0300
Revision 1
| Extractor Lower Bounds, Revisited |
Divesh Aggarwal,
Siyao Guo,
Maciej Obremski,
Joao Ribeiro,
Noah Stephens-Davidowitz
https://eccc.weizmann.ac.il/report/2019/173#revision1We 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).Sat, 20 Jun 2020 00:42:21 +0300https://eccc.weizmann.ac.il/report/2019/173#revision1
Paper TR19-173
| Extractor Lower Bounds, Revisited |
Divesh Aggarwal,
Siyao Guo,
Maciej Obremski,
Joao Ribeiro,
Noah Stephens-Davidowitz
https://eccc.weizmann.ac.il/report/2019/173We 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).Sun, 01 Dec 2019 16:42:42 +0200https://eccc.weizmann.ac.il/report/2019/173