Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-047 | 24th April 2012 21:58

Extractors for Turing-machine sources

RSS-Feed




TR12-047
Authors: Emanuele Viola
Publication: 24th April 2012 21:58
Downloads: 3523
Keywords: 


Abstract:

We obtain the first deterministic randomness extractors
for $n$-bit sources with min-entropy $\ge n^{1-\alpha}$
generated (or sampled) by single-tape Turing machines
running in time $n^{2-16 \alpha}$, for all sufficiently
small $\alpha > 0$. We also show that such machines
cannot sample a uniform $n$-bit input to the Inner
Product function together with the output.

The proofs combine a variant of the crossing-sequence
technique by Hennie [SWCT 1965] with extractors for block
sources, especially those by Chor and Goldreich [SICOMP
1988] and by Kamp, Rao, Vadhan, and Zuckerman [JCSS
2011].



ISSN 1433-8092 | Imprint