dc.contributor.author | Diakonikolas, Ilias | |
dc.contributor.author | Kane, Daniel M. | |
dc.contributor.author | Nelson, Jelani | |
dc.date.accessioned | 2015-01-21T21:50:01Z | |
dc.date.issued | 2010 | |
dc.identifier | Quick submit: 2015-01-13T12:03:53-05:00 | |
dc.identifier.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. | en_US |
dc.identifier.isbn | 978-1-4244-8525-3 | en_US |
dc.identifier.issn | 0272-5428 | en_US |
dc.identifier.uri | http://nrs.harvard.edu/urn-3:HUL.InstRepos:13777005 | |
dc.description.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). | en_US |
dc.description.sponsorship | Engineering and Applied Sciences | en_US |
dc.language.iso | en_US | en_US |
dc.publisher | IEEE | en_US |
dc.relation.isversionof | doi:10.1109/FOCS.2010.8 | en_US |
dc.relation.hasversion | http://arxiv.org/abs/0911.3389 | en_US |
dash.license | LAA | |
dc.title | Bounded Independence Fools Degree-2 Threshold Functions | en_US |
dc.type | Conference Paper | en_US |
dc.date.updated | 2015-01-13T17:03:53Z | |
dc.description.version | Accepted Manuscript | en_US |
dc.rights.holder | Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson | |
dc.relation.journal | 2010 51st IEEE Annual Symposium on Foundations of Computer Science (FOCS) | en_US |
dash.depositing.author | Nelson, Jelani | |
dc.date.available | 2015-01-21T21:50:01Z | |
dc.identifier.doi | 10.1109/FOCS.2010.8 | * |
dash.contributor.affiliated | Nelson, Jelani | |