TY - GEN
T1 - Noise stability is computable and approximately low-dimensional
AU - De, Anindya
AU - Mossel, Elchanan
AU - Neeman, Joe
N1 - Funding Information:
∗ Full version of this paper is available at https://arxiv.org/abs/1701.01483. † E. M. acknowledges the support of grant N00014-16-1-2227 from Office of Naval Research and of NSF award CCF 1320105. A. D. acknowledges the support of a start-up grant from Northwestern University.
Publisher Copyright:
© Anindya De, Elchanan Mossel, and Joe Neeman.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - 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 Rn for n 1 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 an explicit, 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 work.
AB - 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 Rn for n 1 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 an explicit, 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 work.
KW - Gaussian noise stability
KW - Ornstein Uhlenbeck operator
KW - Plurality is stablest
UR - http://www.scopus.com/inward/record.url?scp=85028777916&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028777916&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2017.10
DO - 10.4230/LIPIcs.CCC.2017.10
M3 - Conference contribution
AN - SCOPUS:85028777916
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 32nd Computational Complexity Conference, CCC 2017
A2 - O'Donnell, Ryan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 32nd Computational Complexity Conference, CCC 2017
Y2 - 6 July 2017 through 9 July 2017
ER -