Paper Info
Title
Pseudorandom generators for polynomial threshold functions
Abstract
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.
Year
DOI
Venue
2010
10.1145/1806689.1806749
Clinical Orthopaedics and Related Research
Keywords
DocType
Volume
pseudorandom generator,polynomial threshold function,invariance principles,constant error,pseudorandom generators,log n,n log2,n log,error rate,branching programs,seed-length log n,similar seed length,halfspaces,error parameter,polynomials,threshold functions,seed length o
Conference
42
Issue
ISSN
Citations 
3
0097-5397
29
PageRank 
References 
Authors
1.25
25
2
Name
Order
Citations
PageRank
Raghu Meka148537.05
David Zucherman22588266.65