Bounded Independence Fools Degree-2 Threshold Functions

Ilias Diakonikolas; Daniel M. Kane; Jelani Nelson

doi:10.1109/FOCS.2010.8

Bounded Independence Fools Degree-2 Threshold Functions

Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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}ⁿ 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 language	English
Title of host publication	2010 IEEE 51st Annual Symposium on Foundations of Computer Science
Place of Publication	Los Alamitos, CA, USA
Publisher	Institute of Electrical and Electronics Engineers
Pages	11-20
Number of pages	10
ISBN (Print)	978-1-4244-8525-3
DOIs	https://doi.org/10.1109/FOCS.2010.8
Publication status	Published - 2010

Access to Document

10.1109/FOCS.2010.8

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5670951&tag=1

Cite this

@inproceedings{d7ed511e3a2e461f8293e94eedf150f6,

title = "Bounded Independence Fools Degree-2 Threshold Functions",

abstract = "For an n-variate degree-2 real polynomial p, we prove that Ex\textasciitilde{}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).",

author = "Ilias Diakonikolas and Kane, \{Daniel M.\} and Jelani Nelson",

year = "2010",

doi = "10.1109/FOCS.2010.8",

language = "English",

isbn = "978-1-4244-8525-3",

pages = "11--20",

booktitle = "2010 IEEE 51st Annual Symposium on Foundations of Computer Science",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

}

TY - GEN

T1 - Bounded Independence Fools Degree-2 Threshold Functions

AU - Diakonikolas, Ilias

AU - Kane, Daniel M.

AU - Nelson, Jelani

PY - 2010

Y1 - 2010

N2 - 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).

AB - 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).

U2 - 10.1109/FOCS.2010.8

DO - 10.1109/FOCS.2010.8

M3 - Conference contribution

SN - 978-1-4244-8525-3

SP - 11

EP - 20

BT - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science

PB - Institute of Electrical and Electronics Engineers

CY - Los Alamitos, CA, USA

ER -

Bounded Independence Fools Degree-2 Threshold Functions

Abstract

Access to Document

Fingerprint

Cite this