Pseudorandom bits and lower bounds for randomized Turing machines
Pseudorandom bits and lower bounds for randomized Turing machines
复制标题
随机图灵机的伪随机位和下界
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Emanuele Viola
.本文给出了随机图灵机的一个近似二次拉伸伪随机发生器，它具有一个单向随机带和一个双向工作带。这是该模型的第一个生成器。它的伸展基本上是给定当前下限的最佳可能。我们使用生成器来证明在上面的图灵机模型扩展的双向只读输入带的时间下界。下界的形式是？1 + Ω（1），并且是一个在线性时间内可计算的函数，具有两个量化器交替。以前的下界甚至对于在简单的指数时间内可计算的函数也是未知的。
. We exhibit a pseudorandom generator with nearly quadratic stretch for randomized Turing machines, which have a one-way random tape and a two-way work tape. This is the first generator for this model. Its stretch is essentially the best possible given current lower bounds. We use the generator to prove a time lower bound in the above Turing machine model extended with a two-way read-only input tape. The lower bound is of the form ? 1 + Ω ( 1 ) and is for a function computable in linear time with two quantifier alternations. Previously lower bounds were not known even for functions computable in simply exponential time.
用于以任意顺序读取一次的分支程序的伪随机生成器
DOI：
10.1109/focs.2018.00093
发表时间：
2018
期刊：
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018
影响因子：
--
作者：
Forbes, Michael A.;Kelley, Zander
通讯作者：
Kelley, Zander