Noise stability is computable and approximately low-dimensional

Anindya De, Elchanan Mossel, Joe Neeman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication32nd Computational Complexity Conference, CCC 2017
EditorsRyan O'Donnell
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770408
DOIs
StatePublished - Jul 1 2017
Event32nd Computational Complexity Conference, CCC 2017 - Riga, Latvia
Duration: Jul 6 2017Jul 9 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume79
ISSN (Print)1868-8969

Other

Other32nd Computational Complexity Conference, CCC 2017
CountryLatvia
CityRiga
Period7/6/177/9/17

Keywords

  • Gaussian noise stability
  • Ornstein Uhlenbeck operator
  • Plurality is stablest

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Noise stability is computable and approximately low-dimensional'. Together they form a unique fingerprint.

Cite this