Noise stability is computable and approximately low-dimensional

Anindya De, Elchanan Mossel, Joe Neeman

Research output: Contribution to journalArticlepeer-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 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.

Original languageEnglish (US)
Article number6
JournalTheory of Computing
Volume15
DOIs
StatePublished - 2019

Keywords

  • Computability
  • Gaussian surface area
  • Noise stability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Noise stability is computable and approximately low-dimensional'. Together they form a unique fingerprint.

Cite this