Pseudorandom Generators and Typically-Correct Derandomization
Pseudorandom Generators and Typically-Correct Derandomization
复制标题
伪随机生成器和典型正确的去随机化
DOI：
10.1007/978-3-642-03685-9_43
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Ronen Shaltiel
中科院分区：
文献类型：
--
作者：
Jeff Kinne;D. Melkebeek;Ronen Shaltiel
非随机化领域试图在各种算法设置中提供随机算法的有效确定性模拟。戈德里奇和威格森引入了“典型正确”确定性模拟的概念，这种模拟允许在很少的输入上出错。在本文中，我们从两个方面进一步研究了典型正确非随机化。首先，我们开发了一种基于种子扩展伪随机生成器构建典型正确非随机化的通用方法，这些伪随机生成器是显示其种子的伪随机生成器。我们使用我们的方法在各种算法设置中获得条件和无条件典型正确的非随机化结果。我们证明了我们的技术严格推广了Shaltiel先前基于随机提取器的方法，并简化了一些已知结果的证明。我们还证明，我们的方法适用于算法设置，而早期的工作不适用。例如，我们基于比早期工作中使用的更弱的硬度假设，为BPP中的每种语言提供了典型正确的多项式时间模拟。其次，我们研究了典型正确的非随机化BPP是否包含电路下界。推广了Kabanets和Impagliazzo在零误差情况下的工作，我们建立了Goldreich和Wigderson考虑范围内错误率的正解。在此过程中，我们提供了一个更简单的证明零错误结果的方法。我们的证明比原来的证明尺度更好，并且不依赖于Impagliazzo， Kabanets和Wigderson的结果，即具有多项式大小电路的NEXP意味着NEXP与EXP一致。
The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of “typically-correct” deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.First, we develop a generic approach for constructing typically-correct derandomizations based on seed-extending pseudorandom generators, which are pseudorandom generators that reveal their seed. We use our approach to obtain both conditional and unconditional typically-correct derandomization results in various algorithmic settings. We show that our technique strictly generalizes an earlier approach by Shaltiel based on randomness extractors, and simplifies the proofs of some known results. We also demonstrate that our approach is applicable in algorithmic settings where earlier work did not apply. For example, we present a typically-correct polynomial-time simulation for every language in BPP based on a hardness assumption that is weaker than the ones used in earlier work.Second, we investigate whether typically-correct derandomization of BPP implies circuit lower bounds. Extending the work of Kabanets and Impagliazzo for the zero-error case, we establish a positive answer for error rates in the range considered by Goldreich and Wigderson. In doing so, we provide a simpler proof of the zero-error result. Our proof scales better than the original one and does not rely on the result by Impagliazzo, Kabanets, and Wigderson that NEXP having polynomial-size circuits implies that NEXP coincides with EXP.
多项式时间层次中的硬度放大
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
Dan Gutfreund;Akinori Kawachi
通讯作者：
Akinori Kawachi