Euclidean Partitions Optimizing Noise Stability

2012/11/30 by Steven Heilman, Heilman, Steven
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Limits and Structures in Graph Theory #Metric Geometry (math.MG) #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.1211.7138

openalex publication_date 2012/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Standard Simplex Conjecture of Isaksson and Mossel asks for the partition \A_i\_i=1^k of ℝⁿ into k≤ n+1 pieces of equal Gaussian measure of optimal noise stability. That is, for ρ>0, we maximize ∑_i=1^k∫_ℝⁿ∫_ℝⁿ1_A_i(x)1_A_i(xρ+y√1-ρ²) e^-(x₁²+⋯+x_n²)/2e^-(y₁²+⋯+y_n²)/2dxdy. 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≥2 and 0

Related

• Standard Simplices and Pluralities are Not the Most Noise Stable
• Noise Stability is computable and low dimensional
• Maximally Stable Gaussian Partitions with Discrete Applications
• Hyperstable Sets with Voting and Algorithmic Hardness Applications
• Robust Optimality of Gaussian Noise Stability