Publication: Bounded Independence Fools Degree-2 Threshold Functions
Loading...
Open/View Files
Date
2010
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Diakonikolas, 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.
Abstract
For 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).
Description
Other Available Sources
Research Data
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service