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/epsilon(O(d)) fooling degree d PTFs with error at most epsilon. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error epsilon. For the class of degree 1 threshold functions or halfspaces, previously only PRGs with seed length O(log n log(2)(1/epsilon)/epsilon(2)) were known. We improve this dependence on the error parameter and construct PRGs with seed length O(log n + log(2)(1/epsilon)) that epsilon-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 epsilon for halfspaces. These techniques may be of independent interest.
pseudorandom generators polynomials threshold functions halfspaces invariance principles branching programs