Euclidean partitions optimizing noise stability

DOI10.1214/EJP.V19-3083MaRDI QIDQ743497zbMATH OpenOpenAlexFDO

Authors Steven Heilman

Publication date 24 September 2014

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.7138

zbMATH Keywords

MAX-\(k\)-CUToptimizationpluralitystandard simplexunique games conjecture

Mathematics Subject Classification ID

Probabilistic measure theory (60A10) Gaussian processes (60G15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Abstract: The Standard Simplex Conjecture of Isaksson and Mossel asks for the partition ${A_i}_{i=1}^k$ of $mathbb{R}^n$ into $kleqn+1$ pieces of equal Gaussian measure of optimal noise stability. That is, for $ho>0$, we maximize ${\displaystyle }$ sum_{i=1}^{k}int_{mathbb{R}^{n}}int_{mathbb{R}^{n}}1_{A_{i}}(x)1_{A_{i}}(x ho+ysqrt{1- ho^{2}}) e^{-(x_{1}^{2}+cdots+x_{n}^{2})/2}e^{-(y_{1}^{2}+cdots+y_{n}^{2})/2}dxdy. ${\displaystyle }$ Isaksson and Mossel guessed the best partition for this problem and proved some applications of their conjecture. For example, the Standard Simplex Conjecture implies the Plurality is Stablest Conjecture. For $k=3,ngeq2$ and $0<ho<h{o}_0(k,n)$, we prove the Standard Simplex Conjecture. The full conjecture has applications to theoretical computer science, and to geometric multi-bubble problems (after Isaksson and Mossel).

Recommendations

• Standard simplices and pluralities are not the most noise stable
• Robust optimality of Gaussian noise stability
• Maximally stable Gaussian partitions with discrete applications
• Three candidate plurality is stablest for small correlations
• scientific article; zbMATH DE number 7140483

Cited in

(10)

• Maximally stable Gaussian partitions with discrete applications
• Low correlation noise stability of symmetric sets
• Standard simplices and pluralities are not the most noise stable
• scientific article; zbMATH DE number 6537946 (Why is no real title available?)
• Noise stability is computable and approximately low-dimensional
• A periodic isoperimetric problem related to the unique games conjecture
• Three candidate plurality is stablest for small correlations
• Solution of the propeller conjecture in \(\mathbb{R}^3\)
• Common Information, Noise Stability, and Their Extensions
• Sphere valued noise stability and quantum max-cut hardness

This page was built for publication: Euclidean partitions optimizing noise stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q743497)