More on bounded independence plus noise: Pseudorandom generators for read-once polynomials
More on bounded independence plus noise: Pseudorandom generators for read-once polynomials
复制标题
有关有界独立性和噪声的更多信息：用于读取一次多项式的伪随机生成器
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Chin Ho Lee;Emanuele Viola
我们构造伪随机发生器与改进的种子长度的几类测试。首先，我们考虑GF（2）上m元的只读多项式类。对于误差ε，我们得到种子长度<$（log（m/ε）log（1/ε））。这是最佳的，直到log（1/ε）·polyloglog（m/ε）的因子。先前的最佳种子长度是以m和1/ε为单位的多对数。其次，我们考虑乘积检验f：{0，1}m→ C≤1。这些测试是k个函数fi：{0，1}→C≤1的乘积，其中fi的输入是m个变量的不相交子集，C≤1是复单位圆盘。在这里，我们得到种子长度` ·polylog（m/ε）。这意味着更好的生成器用于其他类别的测试。此外，如果fi具有输出范围{− 1，0，1}，则我们获得种子长度<$（（log（k/ε）+ `）（log（1/ε）+ log logm））。这再次是最优的，直到log（1/ε）· polylog（`，logk，logm，log（1/ε））的因子，而先前的最佳种子长度是≥ logk。我们的证明的一个主要组成部分是表明，这些类的测试是愚弄几乎d-明智的独立分布扰动噪声。ACM分类：G.3 AMS分类：68 Q87，68 W20
We construct pseudorandom generators with improved seed length for several classes of tests. First, we consider the class of read-once polynomials over GF(2) in m variables. For error ε we obtain seed length Õ(log(m/ε) log(1/ε)). This is optimal up to a factor of log(1/ε) ·poly loglog(m/ε). The previous best seed length was polylogarithmic in m and 1/ε . Second, we consider product tests f : {0,1}m→ C≤1. These tests are the product of k functions fi : {0,1}→C≤1, where the inputs of the fi are disjoint subsets of the m variables and C≤1 is the complex unit disk. Here we obtain seed length ` ·polylog(m/ε). This implies better generators for other classes of tests. If moreover the fi have output range {−1,0,1} then we obtain seed length Õ((log(k/ε)+ `)(log(1/ε)+ log logm)). This is again optimal up to a factor of log(1/ε) · polylog(`, logk, logm, log(1/ε)), while the previous best seed length was ≥ √ k. A main component of our proofs is showing that these classes of tests are fooled by almost d-wise independent distributions perturbed with noise. ACM Classification: G.3 AMS Classification: 68Q87, 68W20
用于以任意顺序读取一次的分支程序的伪随机生成器
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