2026-07-23T15:27:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7539 2024-03-06T10:40:11Z ddc:004 open_access

Noise Stability Is Computable and Approximately Low-Dimensional De, Anindya Mossel, Elchanan Neeman, Joe Gaussian noise stability; Plurality is stablest; Ornstein Uhlenbeck operator Questions of noise stability play an important role in hardness of approximation in computer science as well as in the theory of voting. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of R^n for n >= 1 to k parts with given Gaussian measures mu_1, ..., mu_k. We call a partition epsilon-optimal, if its noise stability is optimal up to an additive epsilon. In this paper, we give an explicit, 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 work. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anindya De and Elchanan Mossel and Joe Neeman 2017 Is Part Of LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2017.10 urn:nbn:de:0030-drops-75390 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.10 eng https://creativecommons.org/licenses/by/3.0/legalcode