Bounded Independence Fools Degree-2 Threshold Functions

For an n-variate degree-2 real polynomial p, we prove that E x~D [sig(p(x))] Is determined up to an additive ε as long as D is a k-wise Independent distribution over {-1, 1} n 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).

Authors

• Ilias Diakonikolas
• Daniel M. Kane
• Jelani Nelson

Keywords

• Polynomials
• Approximation methods
• Eigenvalues and eigenfunctions
• Fourier transforms
• Convolution
• Neodymium
• Smoothing methods
• Threshold Function
• Boolean Function
• Fourier Transform
• Upper Bound
• Square Root
• Proof Of Theorem
• Smooth Function
• Taylor Series
• Data Streams
• Approximation Theory
• Smooth Approximation
• Small Eigenvalues
• Univariate Polynomial
• Mollifier
• derandomization
• $k$-wise independence
• polynomial threshold functions