Bounded Independence Fools Degree-2 Threshold Functions
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).Other Sources
http://arxiv.org/abs/0911.3389Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:13777005
Collections
- FAS Scholarly Articles [17845]
Contact administrator regarding this item (to report mistakes or request changes)