research-article

Open access

Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion

Authors:

Dan Mikulincer,

Prasad RaghavendraAuthors Info & Claims

STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

Pages 661 - 671

https://doi.org/10.1145/3564246.3585118

Published: 02 June 2023 Publication History

Abstract

We consider a variant of the classical notion of noise on the Boolean hypercube which gives rise to a new approach to inequalities regarding noise stability. We use this approach to give a new proof of the Majority is Stablest theorem by Mossel, O'Donnell, and Oleszkiewicz, improving the dependence of the bound on the maximal influence of the function from logarithmic to polynomial. We also show that a variant of the conjecture by Courtade and Kumar regarding the most informative Boolean function, where the classical noise is replaced by our notion, holds true. Our approach is based on a stochastic construction that we call the renormalized Brownian motion, which facilitates the use of inequalities in Gaussian space in the analysis of Boolean functions.

References

[1]

Thomas A. Courtade and Gowtham R. Kumar. 2014. Which Boolean functions maximize mutual information on noisy inputs? IEEE Trans. Inform. Theory 60, 8 ( 2014 ), 4515-4525. https://doi.org/10.1109/TIT. 2014.2326877

[2]

Anindya De, Elchanan Mossel, and Joe Neeman. 2016. Majority is stablest: discrete and SoS. Theory Comput. 12 ( 2016 ), Paper No. 4, 50. https://doi.org/10.4086/toc. 2016.v012a004

[3]

Irit Dinur, Elchanan Mossel, and Oded Regev. 2009. Conditional hardness for approximate coloring. SIAM J. Comput. 39, 3 ( 2009 ), 843-873. https://doi.org/10. 1137/07068062X

Digital Library

[4]

Ronen Eldan. 2015. A two-sided estimate for the Gaussian noise stability deficit. Invent. Math. 201, 2 ( 2015 ), 561-624. https://doi.org/10.1007/s00222-014-0556-6

[5]

Ronen Eldan. 2018. Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations. Geometric and Functional Analysis 28, 6 ( 2018 ), 1548-1596.

[6]

Ronen Eldan and Renan Gross. 2022. Concentration on the Boolean hypercube via pathwise stochastic analysis. Inventiones mathematicae ( 2022 ), 1-60.

[7]

Ronen Eldan and Omer Shamir. 2022. Log concavity and concentration of Lipschitz functions on the Boolean hypercube. Journal of Functional Analysis 282, 8 ( 2022 ), 109392.

[8]

Ronen Eldan, Avi Wigderson, and Pei Wu. 2022. An Optimal" It Ain't Over Till It's Over" Theorem. arXiv preprint arXiv:2208.03450 ( 2022 ).

[9]

Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer. 2018. Invariance principle on the slice. ACM Transactions on Computation Theory (TOCT) 10, 3 ( 2018 ), 1-37.

[10]

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. 2007. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37, 1 ( 2007 ), 319-357.

Digital Library

[11]

Guy Kindler, Ryan O'Donnell, and David Witmer. 2015. Remarks on the most informative function conjecture at fixed mean. arXiv preprint arXiv:1506.03167 ( 2015 ).

[12]

Elchanan Mossel. 2010. Gaussian bounds for noise correlation of functions. Geom. Funct. Anal. 19, 6 ( 2010 ), 1713-1756. https://doi.org/10.1007/s00039-010-0047-x

[13]

Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. 2010. Noise stability of functions with low influences: Invariance and optimality. Annals of Mathematics ( 2010 ), 295-341. https://doi.org/10.4007/annals. 2010. 171.295

[14]

Bernt Ø ksendal. 2003. Stochastic diferential equations (sixth ed.). SpringerVerlag, Berlin. xxiv+ 360 pages. https://doi.org/10.1007/978-3-642-14394-6 An introduction with applications.

[15]

Ryan O'Donnell. 2014. Analysis of Boolean functions. Cambridge University Press, New York. xx+ 423 pages. https://doi.org/10.1017/CBO9781139814782

[16]

Or Ordentlich, Ofer Shayevitz, and Omri Weinstein. 2016. An improved upper bound for the most informative boolean function conjecture. In 2016 IEEE International Symposium on Information Theory (ISIT). IEEE, 500-504.

Digital Library

[17]

Emmanuel Rio. 2009. Upper bounds for minimal distances in the central limit theorem. Ann. Inst. Henri Poincaré Probab. Stat. 45, 3 ( 2009 ), 802-817. https: //doi.org/10.1214/08-AIHP187

[18]

Alex Samorodnitsky. 2016. On the entropy of a noisy function. IEEE Transactions on Information Theory 62, 10 ( 2016 ), 5446-5464.

Digital Library

[19]

Cédric Villani. 2008. Optimal transport: old and new. Vol. 338. Springer Science & Business Media.

[20]

Hengjie Yang and Richard D Wesel. 2019. On the most informative boolean functions of the very noisy channel. In 2019 IEEE International Symposium on Information Theory (ISIT). IEEE, 1202-1206.

Digital Library

[21]

Lei Yu. 2021. On the Φ-Stability and Related Conjectures. arXiv preprint arXiv:2104.08740 ( 2021 ).

Cited By

Kireeva AMourrat J(2024)Breakdown of a concavity property of mutual information for non-Gaussian channelsInformation and Inference: A Journal of the IMA10.1093/imaiai/iaae00813:2Online publication date: 5-Apr-2024
https://doi.org/10.1093/imaiai/iaae008
Yu L(2023)On the $$\Phi $$-stability and related conjecturesProbability Theory and Related Fields10.1007/s00440-023-01209-5186:3-4(1045-1080)Online publication date: 12-May-2023
https://doi.org/10.1007/s00440-023-01209-5

Index Terms

Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion
1. Mathematics of computing
  1. Information theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions
ITCS '16: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A ...
Using nondeterminism to amplify hardness
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC '02). We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a ...
Look into the Mirror: Evolving Self-dual Bent Boolean Functions
Genetic Programming
Abstract
Bent Boolean functions are important objects in cryptography and coding theory, and there are several general approaches for constructing such functions. Metaheuristics proved to be a strong choice as they can provide many bent functions, even ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

June 2023

1926 pages

ISBN:9781450399135

DOI:10.1145/3564246

General Chair:
Barna Saha
University of California at San Diego, USA
,
Program Chair:
Rocco A. Servedio
Columbia University, USA

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '23

Sponsor:

SIGACT

STOC '23: 55th Annual ACM Symposium on Theory of Computing

June 20 - 23, 2023

FL, Orlando, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
373
Total Downloads

Downloads (Last 12 months)251
Downloads (Last 6 weeks)35

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kireeva AMourrat J(2024)Breakdown of a concavity property of mutual information for non-Gaussian channelsInformation and Inference: A Journal of the IMA10.1093/imaiai/iaae00813:2Online publication date: 5-Apr-2024
https://doi.org/10.1093/imaiai/iaae008
Yu L(2023)On the $$\Phi $$-stability and related conjecturesProbability Theory and Related Fields10.1007/s00440-023-01209-5186:3-4(1045-1080)Online publication date: 12-May-2023
https://doi.org/10.1007/s00440-023-01209-5

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents