Extractors for Turing-Machine Sources

Extractors for Turing-Machine Sources
复制标题

图灵机源提取器

DOI：
--
复制
发表时间：
2012
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
通讯作者：
Emanuele Viola
Emanuele Viola
中科院分区：
--
文献类型：
--
作者：
Emanuele Viola

文献摘要

被引文献

相似文献

我们得到了由运行在时间n 2 16的单带图灵机产生(或采样)的最小熵为n 1的n比特源的第一个确定性随机性抽取器，对于所有足够小的&gt；0。我们还表明，这样的机器不能对内积函数的n位输入和输出进行统一的采样。这些证明结合了Hennie[SWCT 1965]的交叉序列技术的变体与块源的提取程序，特别是Chor和Goldreich[SICOMP 1988]以及Kamp、Rao、Vadhan和Zuckerman的提取程序[JCS 2011]。
We obtain the rst deterministic randomness extractors for n-bit sources with minentropy n 1 generated (or sampled) by single-tape Turing machines running in time n 2 16 , for all suciently small > 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].