Pseudorandom generators for polynomial threshold functions
Pseudorandom generators for polynomial threshold functions
复制标题
多项式阈值函数的伪随机生成器
DOI：
10.1145/1806689.1806749
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
Raghu Meka;David Zuckerman
我们研究了为低度多项式阈值函数（PTF）构建伪和生成器的自然问题。对于二次阈值函数和恒定误差ε，也不知道非平凡的构造。在误差参数ε上，并获得以下结果。 ≥1/poly（log n）。尺寸单位球。
我们的构造和分析的主要主题是使用不变性原理来构建伪和生成器具有独立的利益。
We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n/εO(d) fooling degree d PTFs with error at most ε. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error ε. For the class of degree 1 threshold functions or halfspaces, we construct PRGs with much better dependence on the error parameter ε and obtain the following results. A PRG with seed length O(log n log(1/ε)) for error ε ≥ 1/poly(n). A PRG with seed length O(log n) for ε ≥ 1/poly(log n). Previously, only PRGs with seed length O(log n log2(1/ε)/ ε2) were known for halfspaces. We also obtain PRGs with similar seed lengths for fooling halfspaces over the $n$ dimensional unit sphere.
The main theme of our constructions and analysis is the use of invariance principles to construct pseudorandom generators. We also introduce the notion of monotone read-once branching programs, which is key to improving the dependence on the error rate ε for halfspaces. These techniques may be of independent interest.