Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/2688073.2688076acmconferencesArticle/Chapter ViewAbstractPublication PagesitcsConference Proceedingsconference-collections
abstract

Standard Simplices and Pluralities are Not the Most Noise Stable

Published: 11 January 2015 Publication History

Abstract

The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discretenoise stability respectively. These two conjectures are natural generalizations of the Gaussian noise stability result by Borell (1985) and the Majority is Stablest Theorem (2004). Here we show that the standard simplex is not the most stable partition in Gaussian space and that Plurality is not the most stable low inuence partition in discrete space for every number of parts k > 3, for every value ρ ≠ of the noise and for every prescribed measures for the different parts as long as they are not all equal to 1/k. Our results do not contradict the original statements of the Plurality is Stablest and Standard Simplex Conjectures concerning partitions into sets of equal measure. However, they indicate that if these conjectures are true, their veracity and their proofs will crucially rely on assuming that the sets are of equal measures, in stark contrast to Borell's result, the Majority is Stablest Theorem and many other results in isoperimetric theory.
In other words, the optimal partitions for noise stability are of a different nature than the ones considered for partitions into three parts in isoperimetric theory. In the latter case, the standard simplex is the partition of the plane into three sets of smallest Gaussian perimeter, where the sets are restricted to have Gaussian measures a1, a2, a3 > 0 respectively, with a1 + a2 + a3 = 1 and |ai --1/3| < .04 for all i ∈ {1, 2, 3}. Thus, we now know that the extension of noise stability theory from two to three or more parts is very much different than the extension of isoperimetric theory from two to three or more parts. Moreover, all existing proofs which optimize noise stability of two sets must fail for more than three sets, since these proofs rely on the fact that a half-space optimizes noise stability with respect to any measure restriction. Given our results it is natural to ask for (conjectured) partitions achieving the optimum noise stability.
The main new ingredient in our work shows that the Ornstein-Uhlenbeck operator applied to the indicator function of a simplicial cone becomes holomorphic when restricted to certain lines. This holomorphicity condition, when combined with a first variation argument (i.e. an innite dimensional perturbative argument of the rst order), then shows that any simplicial cone can be perturbed in a volume-preserving manner to improve its noise stability. Such a holomorphicity argument seems unavailable for the is operimetric problem, since this argument uses the inherent non-locality of the Ornstein-Uhlenbeck semigroup.
A full version of the paper is available at arXiv:1403.0885

Cited By

View all
  • (2016)Decidability of Non-interactive Simulation of Joint Distributions2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.65(545-554)Online publication date: Oct-2016
  • (2014)Euclidean partitions optimizing noise stabilityElectronic Journal of Probability10.1214/EJP.v19-308319:noneOnline publication date: 1-Jan-2014

Index Terms

  1. Standard Simplices and Pluralities are Not the Most Noise Stable

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ITCS '15: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science
    January 2015
    404 pages
    ISBN:9781450333337
    DOI:10.1145/2688073
    Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 11 January 2015

    Check for updates

    Author Tags

    1. noise stability
    2. plurality
    3. standard simplex

    Qualifiers

    • Abstract

    Funding Sources

    Conference

    ITCS'15
    Sponsor:
    ITCS'15: Innovations in Theoretical Computer Science
    January 11 - 13, 2015
    Rehovot, Israel

    Acceptance Rates

    ITCS '15 Paper Acceptance Rate 45 of 159 submissions, 28%;
    Overall Acceptance Rate 172 of 513 submissions, 34%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2016)Decidability of Non-interactive Simulation of Joint Distributions2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.65(545-554)Online publication date: Oct-2016
    • (2014)Euclidean partitions optimizing noise stabilityElectronic Journal of Probability10.1214/EJP.v19-308319:noneOnline publication date: 1-Jan-2014

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media