Theory of Computing
-------------------
Title     : Noise Stability is Computable and Approximately Low-Dimensional
Authors   : Anindya De, Elchanan Mossel, and Joe Neeman
Volume    : 15
Number    : 6
Pages     : 1-47
URL       : https://theoryofcomputing.org/articles/v015a006

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^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).