Noise stability is computable and approximately low-dimensional

Anindya De; Elchanan Mossel; Joe Neeman

doi:10.4086/toc.2019.v015a006

Noise stability is computable and approximately low-dimensional

Anindya De, Elchanan Mossel, Joe Neeman

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

The notion of Gaussian noise stability plays an important role in hardness of approximation in theoretical computer science as well as in the theory of voting. The Gaussian noise stability of a partition of Rⁿ is simply the probability that two correlated Gaussian vectors both fall into the same part. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of Rⁿ to k parts with given Gaussian measures µ₁, …, µ_k . We call a partition ε-optimal, if its noise stability is optimal up to an additive ε. In this paper, we give a computable function n(ε) such that an ε-optimal partition exists in R^n(ε). This result has implications for the computability of certain problems in non-interactive simulation, which are addressed in a subsequent paper.

Original language	English (US)
Article number	6
Journal	Theory of Computing
Volume	15
DOIs	https://doi.org/10.4086/toc.2019.v015a006
State	Published - 2019

Funding

Supported by NSF grant CCF 1926872 (transferred from CCF 1814706). Most of the work done as a faculty at Northwestern University. Supported by DMS-1737944 and ONR N00014-16-1-2227, N00014-17-1-2598. Funded by a Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) under GermanyâĂŹs Excellence Strategy GZ 2047/1, Projekt-ID 390685813 and a Sloan Fellowship. A conference version of this paper appeared in the Proceedings of the 32nd Computational Complexity Conference, 2017. ∗Supported by NSF grant CCF 1926872 (transferred from CCF 1814706). Most of the work done as a faculty at Northwestern University. †Supported by DMS-1737944 and ONR N00014-16-1-2227, N00014-17-1-2598. ‡Funded by a Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) under GermanyâA˘ Źs Excellence Strategy GZ 2047/1, Projekt-ID 390685813 and a Sloan Fellowship.

Keywords

Computability
Gaussian surface area
Noise stability

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Access to Document

10.4086/toc.2019.v015a006

Cite this

@article{b40757d96d694710a6e609e732c66a4a,

title = "Noise stability is computable and approximately low-dimensional",

abstract = "The notion of Gaussian noise stability plays an important role in hardness of approximation in theoretical computer science as well as in the theory of voting. The Gaussian noise stability of a partition of Rn is simply the probability that two correlated Gaussian vectors both fall into the same part. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of Rn to k parts with given Gaussian measures µ1, …, µk . We call a partition ε-optimal, if its noise stability is optimal up to an additive ε. In this paper, we give a computable function n(ε) such that an ε-optimal partition exists in Rn(ε). This result has implications for the computability of certain problems in non-interactive simulation, which are addressed in a subsequent paper.",

keywords = "Computability, Gaussian surface area, Noise stability",

author = "Anindya De and Elchanan Mossel and Joe Neeman",

note = "Funding Information: Supported by NSF grant CCF 1926872 (transferred from CCF 1814706). Most of the work done as a faculty at Northwestern University. Supported by DMS-1737944 and ONR N00014-16-1-2227, N00014-17-1-2598. Funded by a Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) under Germany{\^a}{\u A}{\'Z}s Excellence Strategy GZ 2047/1, Projekt-ID 390685813 and a Sloan Fellowship. Funding Information: A conference version of this paper appeared in the Proceedings of the 32nd Computational Complexity Conference, 2017. ∗Supported by NSF grant CCF 1926872 (transferred from CCF 1814706). Most of the work done as a faculty at Northwestern University. †Supported by DMS-1737944 and ONR N00014-16-1-2227, N00014-17-1-2598. ‡Funded by a Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) under Germany{\^a}A˘ {\'Z}s Excellence Strategy GZ 2047/1, Projekt-ID 390685813 and a Sloan Fellowship. Publisher Copyright: {\textcopyright} 2019 Anindya De, Elchanan Mossel, and Joe Neeman.",

year = "2019",

doi = "10.4086/toc.2019.v015a006",

language = "English (US)",

volume = "15",

journal = "Theory of Computing",

issn = "1557-2862",

publisher = "University of Chicago, Department of Computer Science",

}

TY - JOUR

T1 - Noise stability is computable and approximately low-dimensional

AU - De, Anindya

AU - Mossel, Elchanan

AU - Neeman, Joe

N1 - Funding Information: Supported by NSF grant CCF 1926872 (transferred from CCF 1814706). Most of the work done as a faculty at Northwestern University. Supported by DMS-1737944 and ONR N00014-16-1-2227, N00014-17-1-2598. Funded by a Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) under GermanyâĂŹs Excellence Strategy GZ 2047/1, Projekt-ID 390685813 and a Sloan Fellowship. Funding Information: A conference version of this paper appeared in the Proceedings of the 32nd Computational Complexity Conference, 2017. ∗Supported by NSF grant CCF 1926872 (transferred from CCF 1814706). Most of the work done as a faculty at Northwestern University. †Supported by DMS-1737944 and ONR N00014-16-1-2227, N00014-17-1-2598. ‡Funded by a Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) under GermanyâA˘ Źs Excellence Strategy GZ 2047/1, Projekt-ID 390685813 and a Sloan Fellowship. Publisher Copyright: © 2019 Anindya De, Elchanan Mossel, and Joe Neeman.

PY - 2019

Y1 - 2019

N2 - The notion of Gaussian noise stability plays an important role in hardness of approximation in theoretical computer science as well as in the theory of voting. The Gaussian noise stability of a partition of Rn is simply the probability that two correlated Gaussian vectors both fall into the same part. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of Rn to k parts with given Gaussian measures µ1, …, µk . We call a partition ε-optimal, if its noise stability is optimal up to an additive ε. In this paper, we give a computable function n(ε) such that an ε-optimal partition exists in Rn(ε). This result has implications for the computability of certain problems in non-interactive simulation, which are addressed in a subsequent paper.

AB - The notion of Gaussian noise stability plays an important role in hardness of approximation in theoretical computer science as well as in the theory of voting. The Gaussian noise stability of a partition of Rn is simply the probability that two correlated Gaussian vectors both fall into the same part. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of Rn to k parts with given Gaussian measures µ1, …, µk . We call a partition ε-optimal, if its noise stability is optimal up to an additive ε. In this paper, we give a computable function n(ε) such that an ε-optimal partition exists in Rn(ε). This result has implications for the computability of certain problems in non-interactive simulation, which are addressed in a subsequent paper.

KW - Computability

KW - Gaussian surface area

KW - Noise stability

UR - http://www.scopus.com/inward/record.url?scp=85076199839&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076199839&partnerID=8YFLogxK

U2 - 10.4086/toc.2019.v015a006

DO - 10.4086/toc.2019.v015a006

M3 - Article

AN - SCOPUS:85076199839

SN - 1557-2862

VL - 15

JO - Theory of Computing

JF - Theory of Computing

M1 - 6

ER -

Noise stability is computable and approximately low-dimensional

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this