Euclidean partitions optimizing noise stability. (English) Zbl 1364.60010

Heilman, Steven

Electron. J. Probab. 19, Paper No. 71, 37 p. (2014).

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

MSC:

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

Keywords:

standard simplex; plurality; optimization; MAX-\(k\)-CUT; unique games conjecture

Citations:

Zbl 1256.60017