Constant-Error Pseudorandomness Proofs from Hardness Require Majority
Constant-Error Pseudorandomness Proofs from Hardness Require Majority
复制标题
硬度的恒定误差伪随机性证明需要多数票
DOI：
10.1145/3322815
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Emanuele Viola
1980年代和1990年代的研究展示了如何从很难计算超过99％输入的功能的功能中构造伪随机生成器。然而，最近的一系列作品表明，如果发电机的误差较小，那么正确性证明就无法在TC0的子类中实现，因此不能将构造应用于已知的硬度结果。本文考虑了典型的伪和生成器构造，并证明了误差较大的情况的类似结果。
Research in the 1980s and 1990s showed how to construct a pseudorandom generator from a function that is hard to compute on more than 99% of the inputs. A more recent line of works showed, however, that if the generator has small error, then the proof of correctness cannot be implemented in subclasses of TC0, and hence the construction cannot be applied to the known hardness results. This article considers a typical class of pseudorandom generator constructions, and proves an analogous result for the case of large error.
具有建议的自适应程序的不可区分性以及硬度放大证明的下限
DOI：
10.1109/focs.2018.00094
发表时间：
2018
期刊：
FOCS
影响因子：
--
作者：
Grinberg, Aryeh;Shaltiel, Ronen;Viola, Emanuele
通讯作者：
Viola, Emanuele