Pseudorandom generators for polynomial threshold functions

摘要

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, previously only PRGs with seed length O(log n log~2(1/ε)/ε2) were known. We improve this dependence on the error parameter and construct PRGs with seed length O(log n + log ~2(1/ε)) that ε-fool 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 PRGs. 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.