A Polylogarithmic PRG for Degree $2$ Threshold Functions in the Gaussian Setting
A Polylogarithmic PRG for Degree $2$ Threshold Functions in the Gaussian Setting
复制标题
高斯设置下 2$ 次阈值函数的多对数 PRG
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
D. Kane
中科院分区：
文献类型：
--
作者：
D. Kane
我们针对高斯测度构建并分析了一种新的用于二次多项式阈值函数的伪随机生成器。特别地，我们得到了一种其种子长度在维度和期望误差两方面都是多项对数的生成器，这相对于现有构造是一个重大改进。
我们的生成器是通过对针对一次读分支程序的伪随机生成器进行适当加权平均而得到的。该分析需要一些思路，包括混合论证以及一个结构结果，这个结构结果使我们能够将我们的二次阈值函数视为若干线性多项式和一个近似线性多项式的函数。
We construct and analyze a new pseudorandom generator for degree 2 polynomial threshold functions with respect to the Gaussian measure. In particular, we obtain one whose seed length is polylogarithmic in both the dimension and the desired error, a substantial improvement over existing constructions.
Our generator is obtained as an appropriate weighted average of pseudorandom generators against read once branching programs. The analysis requires a number of ideas including a hybrid argument and a structural result that allows us to treat our degree 2 threshold function as a function of a number of linear polynomials and one approximately linear polynomial.