摘要：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 µ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 R
n(ε)
. This result has implications for the computability of certain problems in
non-interactive simulation, which are addressed in a subsequent paper.
