Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MACIEJ OBREMSKI:
All reports by Author Maciej Obremski:

TR19-173 | 28th November 2019
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

Extractor Lower Bounds, Revisited

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 ... more >>>




ISSN 1433-8092 | Imprint