research-article

Open access

Fooling Gaussian PTFs via local hyperconcentration

Authors:

Ryan O'Donnell,

Rocco A. Servedio,

Li-Yang TanAuthors Info & Claims

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Pages 1170 - 1183

https://doi.org/10.1145/3357713.3384281

Published: 22 June 2020 Publication History

PDF eReader

Abstract

We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length d ^O(logd) · logn. All previous generators had a seed length with at least a 2^d dependence on d.

The key new ingredient is our Local Hyperconcentration Theorem, which shows that every degree-d Gaussian polynomial is hyperconcentrated almost everywhere at scale d ^−O(logd).

References

[1]

Anthony Carbery and James Wright. 2001. Distributional and L^q norm inequalities for polynomials over convex bodies in R^n. Mathematical Research Letters, 8, 3 (2001), 233–248.

Crossref

Google Scholar

[2]

Ilias Diakonikolas, Daniel Kane, and Jelani Nelson. 2010. Bounded independence fools degree-2 threshold functions. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS). 11–20.

Digital Library

Google Scholar

[3]

Daniel Kane. 2011. k-Independent Gaussians Fool Polynomial Threshold Functions. In Proceedings of the 26th Conference on Computational Complexity (CCC). 252–261.

Digital Library

Google Scholar

[4]

Daniel Kane. 2011. A Small PRG for Polynomial Threshold Functions of Gaussians. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS). 257–266.

Digital Library

Google Scholar

[5]

Daniel Kane. 2012. A structure theorem for poorly anticoncentrated Gaussian chaoses and applications to the study of polynomial threshold functions. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS). 91–100.

Digital Library

Google Scholar

[6]

Daniel Kane. 2014. A pseudorandom generator for polynomial threshold functions of Gaussians with subpolynomial seed length. In Proceedings of the 29th Annual Conference on Computational Complexity (CCC). 217–228.

Digital Library

Google Scholar

[7]

Daniel Kane. 2015. A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting. In Proceedings of the 30th Conference on Computational Complexity (CCC). 567–581.

Google Scholar

[8]

Pravesh Kothari and Raghu Meka. 2015. Almost Optimal Pseudorandom Generators for Spherical Caps. In Proceedings of the 47th Annual on Symposium on Theory of Computing (STOC). 247–256.

Digital Library

Google Scholar

[9]

Raghu Meka and David Zuckerman. 2010. Pseudorandom generators for polynomial threshold functions. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC). 427–436.

Digital Library

Google Scholar

[10]

Raghu Meka and David Zuckerman. 2013. Pseudorandom generators for polynomial threshold functions. SIAM J. Comput., 42, 3 (2013), 1275–1301.

Digital Library

Google Scholar

[11]

Ryan O’Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press. Available at http://analysisofbooleanfunctions.net/

Google Scholar

Cited By

View all

Diakonikolas IKane DKontonis VLiu SZarifis NMohar BShinkar IO'Donnell R(2024)Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649776(152-159)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649776
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
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
Show More Cited By

Index Terms

Fooling Gaussian PTFs via local hyperconcentration
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Pseudorandomness and derandomization

Recommendations

Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

The degree-d Chow parameters of a Boolean function are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded ...
Average-case hardness of NP from exponential worst-case hardness assumptions
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)...
Unexpected hardness results for Kolmogorov complexity under uniform reductions
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 2020

1429 pages

ISBN:9781450369794

DOI:10.1145/3357713

General Chairs:
Konstantin Makarychev
Northwestern University, USA
,
Yury Makarychev
Toyota Technological Institute at Chicago, USA
,
Madhur Tulsiani
Toyota Technological Institute at Chicago, USA
,
Gautam Kamath
University of Waterloo, Canada
,
Program Chair:
Julia Chuzhoy
Toyota Technological Institute at Chicago, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '20

Sponsor:

SIGACT

STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 22 - 26, 2020

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
597
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)9

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Diakonikolas IKane DKontonis VLiu SZarifis NMohar BShinkar IO'Donnell R(2024)Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649776(152-159)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649776
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
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
Arunachalam SYao PLeonardi SGupta A(2022)Positive spectrahedra: invariance principles and pseudorandom generatorsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519965(208-221)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519965

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)

Average-case hardness of NP from exponential worst-case hardness assumptions

Unexpected hardness results for Kolmogorov complexity under uniform reductions