Article

Bounded Independence Fools Degree-2 Threshold Functions

Authors:

Ilias Diakonikolas,

Daniel M. Kane,

Jelani NelsonAuthors Info & Claims

FOCS '10: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science

Pages 11 - 20

https://doi.org/10.1109/FOCS.2010.8

Published: 23 October 2010 Publication History

Publisher Site

Abstract

For an $n$-variate degree–$2$ real polynomial $p$, we prove that $\E_{x\sim \mathcal{D}}[\sgn(p(x))]$ is determined up to an additive $\eps$ as long as $\mathcal{D}$ is a $k$-wise independent distribution over $\bits^n$ for $k = \poly(1/\eps)$. 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).

Cited By

View all

De ALi HNadimpalli SServedio RMohar BShinkar IO'Donnell R(2024)Detecting Low-Degree TruncationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649633(1027-1038)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649633
Diakonikolas IKane DKontonis VLiu SZarifis NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Efficient testable learning of halfspaces with adversarial label noiseProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667836(39470-39490)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667836
Diakonikolas IKane DRen LKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Near-optimal cryptographic hardness of agnostically learning halfspaces and ReLU regression under Gaussian marginalsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618722(7922-7938)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618722
Show More Cited By

Recommendations

Polynomial threshold functions and Boolean threshold circuits

We initiate a comprehensive study of the complexity of computing Boolean functions by polynomial threshold functions (PTFs) on general Boolean domains (as opposed to domains such as { 0 , 1 } n or { - 1 , 1 } n that enforce multilinearity). A typical ...
Bounded Relativization
CCC '23: Proceedings of the conference on Proceedings of the 38th Computational Complexity Conference

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called bounded relativization. For a complexity ...
Extremal properties of polynomial threshold functions

In this paper we give new extremal bounds on polynomial threshold function (PTF) representations of Boolean functions. Our results include the following:*Almost every Boolean function has PTF degree at most n2+O(nlogn). Together with results of Anthony ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOCS '10: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science

October 2010

782 pages

ISBN:9780769542447

Publisher

IEEE Computer Society

United States

Publication History

Published: 23 October 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

De ALi HNadimpalli SServedio RMohar BShinkar IO'Donnell R(2024)Detecting Low-Degree TruncationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649633(1027-1038)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649633
Diakonikolas IKane DKontonis VLiu SZarifis NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Efficient testable learning of halfspaces with adversarial label noiseProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667836(39470-39490)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667836
Diakonikolas IKane DRen LKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Near-optimal cryptographic hardness of agnostically learning halfspaces and ReLU regression under Gaussian marginalsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618722(7922-7938)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618722
Gollakota AKlivans AKothari PSaha BServedio R(2023)A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher ComplexityProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585206(1657-1670)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585206
Kelley ZMeka R(2022)Random restrictions and PRGs for PTFs in gaussian spaceProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.21(1-24)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.21
O’Donnell RServedio RTan L(2022)Fooling PolytopesJournal of the ACM10.1145/346053269:2(1-37)Online publication date: 31-Jan-2022
https://dl.acm.org/doi/10.1145/3460532
Diakonikolas IKane DZarifis NLarochelle HRanzato MHadsell RBalcan MLin H(2020)Near-optimal SQ lower bounds for agnostically learning halfspaces and ReLUs under Gaussian marginalsProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3496864(13586-13596)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3496864
O'Donnell RServedio RTan LMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Fooling Gaussian PTFs via local hyperconcentrationProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384281(1170-1183)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384281
Chattopadhyay EDe AServedio RAceto L(2019)Simple and efficient pseudorandom generators from gaussian processesProceedings of the 34th Computational Complexity Conference10.4230/LIPIcs.CCC.2019.4(1-33)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.4
Boppana RHåstad JLee CViola E(2019)Bounded Independence versus Symmetric TestsACM Transactions on Computation Theory10.1145/333778311:4(1-27)Online publication date: 11-Jul-2019
https://dl.acm.org/doi/10.1145/3337783
Show More Cited By

Abstract

Cited By

Recommendations

Polynomial threshold functions and Boolean threshold circuits

Bounded Relativization

Extremal properties of polynomial threshold functions

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations