Volume 15 (2019) Article 6 pp. 1-47
CCC 2017 Special Issue

Noise Stability is Computable and Approximately Low-Dimensional

by Anindya De, Elchanan Mossel, and Joe Neeman

Received: September 13, 2017
Revised: July 7, 2019
Published: October 11, 2019

$ \newcommand{\R}{{\mathbb R}} $

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^n$ 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^n$ to $k$ parts with given Gaussian measures $\mu_1,\ldots,\mu_k$. We call a partition $\epsilon$-optimal, if its noise stability is optimal up to an additive $\epsilon$. In this paper, we give a computable function $n(\epsilon)$ such that an $\epsilon$-optimal partition exists in $\R^{n(\epsilon)}$. This result has implications for the computability of certain problems in non-interactive simulation, which are addressed in a subsequent paper.

A conference version of this paper appeared in the Proceedings of the 32nd Computational Complexity Conference (CCC'17).

DOI: 10.4086/toc.2019.v015a006

© 2019 Anindya De, Elchanan Mossel, and Joe Neeman
Licensed under a Creative Commons Attribution License (CC-BY)