文章基本信息

标题：Noise Stability is Computable and Approximately Low-Dimensional
本地全文：下载
作者：Anindya De ; Elchanan Mossel ; Joe Neeman 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2019
卷号：15
页码：1-47
DOI：10.4086/toc.2019.v015a006
出版社：University of Chicago
摘要：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.
关键词：noise stability; Gaussian surface area; computability