Show simple item record

dc.contributor.authorDiakonikolas, Ilias
dc.contributor.authorKane, Daniel M.
dc.contributor.authorNelson, Jelani
dc.date.accessioned2015-01-21T21:50:01Z
dc.date.issued2010
dc.identifierQuick submit: 2015-01-13T12:03:53-05:00
dc.identifier.citationDiakonikolas, 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.isbn978-1-4244-8525-3en_US
dc.identifier.issn0272-5428en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:13777005
dc.description.abstractFor 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.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherIEEEen_US
dc.relation.isversionofdoi:10.1109/FOCS.2010.8en_US
dc.relation.hasversionhttp://arxiv.org/abs/0911.3389en_US
dash.licenseLAA
dc.titleBounded Independence Fools Degree-2 Threshold Functionsen_US
dc.typeConference Paperen_US
dc.date.updated2015-01-13T17:03:53Z
dc.description.versionAccepted Manuscripten_US
dc.rights.holderIlias Diakonikolas, Daniel M. Kane, Jelani Nelson
dc.relation.journal2010 51st IEEE Annual Symposium on Foundations of Computer Science (FOCS)en_US
dash.depositing.authorNelson, Jelani
dc.date.available2015-01-21T21:50:01Z
dc.identifier.doi10.1109/FOCS.2010.8*
dash.contributor.affiliatedNelson, Jelani


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record