Bounded Independence Fools Degree-2 Threshold Functions

Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

For an n-variate degree-2 real polynomial p, we prove that Ex~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).

Original languageEnglish
Title of host publication2010 IEEE 51st Annual Symposium on Foundations of Computer Science
Place of PublicationLos Alamitos, CA, USA
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages11-20
Number of pages10
ISBN (Print)978-1-4244-8525-3
DOIs
Publication statusPublished - 2010

Fingerprint Dive into the research topics of 'Bounded Independence Fools Degree-2 Threshold Functions'. Together they form a unique fingerprint.

Cite this