Pseudorandomness from Shrinkage
Pseudorandomness from Shrinkage
复制标题
DOI：
10.1145/3230630
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
R. Impagliazzo;Raghu Meka;David Zuckerman
中科院分区：
文献类型：
--
作者：
R. Impagliazzo;Raghu Meka;David Zuckerman
在过去的几十年里，复杂性理论和伪随机性的一个强有力的主题是使用下界来给出伪随机生成器（PRG）。然而，一般的结果，使用这种硬度与随机性范式遭受定量损失的参数，因此不给非平凡的影响模型，我们不知道超多项式的下限，但知道一个固定的多项式的下限。我们表明，当这样的下限证明使用随机限制，我们可以构建PRG基本上是最好的可能，而不反过来提高下限。更具体地说，假设一个电路族具有收缩指数Γ，如果一个随机约束使p部分变量未设置，则该电路族中任何电路的大小缩小了pΓ+o（1）倍。我们的PRG使用长度为s1/（Γ+1）+o（1）的种子来欺骗大小为s的家族中的电路。利用这一一般构造，我们得到了具有多项式小误差的PRG，其大小为s，种子长度为：1）对于de Morgan公式，种子长度为s1/3+o（1）; 2）对于任意基上的公式，种子长度为s1/2+o（1）; 3）对于只读de Morgan公式，种子长度为s.234 + o（1）。4)对于大小为s的分支程序，种子长度为s1/2+o（1）。这些类已知的以前最好的PRG使用长度大于n/2的种子来输出n位，并且只有当大小s = O（n）[1]时才工作。
One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don't know superpolynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs which are essentially best possible without in turn improving the lower bounds. More specifically, say that a circuit family has shrinkage exponent Γ if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of pΓ+o(1). Our PRG uses a seed of length s1/(Γ+1)+o(1) to fool circuits in the family of size s. By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size s and with the following seed lengths: 1) For de Morgan formulas, seed length s1/3+o(1); 2) For formulas over an arbitrary basis, seed length s1/2+o(1); 3) For read-once de Morgan formulas, seed length s.234...; 4) For branching programs of size s, seed length s1/2+o(1). The previous best PRGs known for these classes used seeds of length bigger than n/2 to output n bits, and worked only when the size s = O(n) [1].