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 TR18-116 | 11th September 2018 22:56

Existence of Simple Extractors

RSS-Feed




Revision #1
Authors: Xue Chen, David Zuckerman
Accepted on: 11th September 2018 22:56
Downloads: 46
Keywords: 


Abstract:

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.


Paper:

TR18-116 | 18th June 2018 09:44

Existence of Simple Extractors





TR18-116
Authors: Xue Chen, David Zuckerman
Publication: 18th June 2018 16:25
Downloads: 377
Keywords: 


Abstract:

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