Euclidean partitions optimizing noise stability

DOI10.1214/EJP.V19-3083zbMATH Open1364.60010arXiv1211.7138OpenAlexW2091629973MaRDI QIDQ743497FDOQ743497

Authors: Steven Heilman 

Publication date: 24 September 2014

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

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).

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

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

zbMATH Keywords

optimizationunique games conjecturepluralitystandard simplexMAX-\(k\)-CUT

Mathematics Subject Classification ID

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

Cited In (6)

• Three candidate plurality is stablest for small correlations
• Standard simplices and pluralities are not the most noise stable
• Common Information, Noise Stability, and Their Extensions
• Maximally stable Gaussian partitions with discrete applications
• Title not available (Why is that?)
• Low correlation noise stability of symmetric sets

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)