Bounded Independence Fools Degree-2 Threshold Functions

Abstract

For an n-variate degree-2 real polynomial p, we prove that E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x~D</sub> [sig(p(x))] Is determined up to an additive ε as long as D is a k-wise Independent distribution over {-1, 1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> for k = poly(1/ε). This gives a broad class of explicit pseudorandom generators against degree-2 boolean threshold functions, and answers an open question of Diakonikolas et al. (FOCS 2009).

Locations

• arXiv (Cornell University) - View - PDF
• CiteSeer X (The Pennsylvania State University) - View - PDF
• Digital Access to Scholarship at Harvard (DASH) (Harvard University) - View - PDF