Diakonikolas, IliasKane, Daniel M.Nelson, Jelani2015-01-212010Diakonikolas, Ilias, Daniel M. Kane, and Jelani Nelson. 2010. "Bounded Independence Fools Degree-2 Threshold Functions." Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 23-26 October 2010, Las Vegas, NV: 11-20. New York, NY: IEEE.978-1-4244-8525-30272-5428http://nrs.harvard.edu/urn-3:HUL.InstRepos:13777005For an n-variate degree-2 real polynomial p, we prove that \(E_{x\sim D}[sig(p(x))]\) Is determined up to an additive \(\epsilon\) as long as D is a k-wise Independent distribution over \(\{-1, 1\}^n\) for \(k = poly(1/\epsilon)\). 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).en-USConference Paper2015-01-13Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson2015-01-2110.1109/FOCS.2010.8