@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???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.",
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",
}