Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-116 | 18th June 2018 09:44

Existence of Simple Extractors


Authors: Xue Chen, David Zuckerman
Publication: 18th June 2018 16:25
Downloads: 160


We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n \cdot 2^m/\epsilon^2)$ seeds, $Ext$ restricted to these seeds is a $(k,3\epsilon)$-extractor. Note that the degree of this restricted extractor is essentially optimal for $m=O(1)$. By combining this with the Leftover Hash Lemma, we deduce that there are strong extractors outputting a constant number of bits with essentially optimal degree where each seed is a linear function, or even a Toeplitz matrix, or a simply-implementable hash function. Although linear extractors were known, such as the one by Trevisan \cite{Trevisan}, it didn't have close to optimal degree (although it did output more bits), and it wasn't known that most sets of linear functions give extractors.

While a simple application of the basic probabilistic method shows the existence of ordinary strong extractors, this approach fails to show the existence of the restricted extractors we seek, or even linear extractors. We therefore adopt a more sophisticated approach, using chaining as used by Rudra and Wootters \cite{RW} and others, combined with the Beck-Fiala theorem from discrepancy theory.

ISSN 1433-8092 | Imprint