Euclidean partitions optimizing noise stability. (English) Zbl 1364.60010

Summary: The Standard Simplex Conjecture of M. Isaksson and E. Mossel [Isr. J. Math. 189, 347–396 (2012; Zbl 1256.60017)] asks for the partition \(\{A_i\}_{i=1}^k\) of \(\mathbb{R}^n\) into \(k\leq n+1\) pieces of equal Gaussian measure of optimal noise stability. That is, for \(\rho>0\), we maximize \[ \sum_{i=1}^k\int_{\mathbb{R}^n}\int_{\mathbb{R}^n}1_{A_i}(x)1_{A_i}(x\rho+y\sqrt{1-\rho^2})e^{-(x_1^2+\ldots +x_n^2)/2}e^{-(y_1^2+\ldots+y_n^2)/2}\,dx\,dy. \]
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,n\geq2\) and \(0<\rho<\rho_{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).


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


Zbl 1256.60017
Full Text: DOI arXiv