Maximally stable Gaussian partitions with discrete applications

DOI10.1007/s11856-011-0181-7zbMath1256.60017arXiv0903.3362OpenAlexW2171695231MaRDI QIDQ1760364

Marcus Isaksson, Elchanan Mossel

Publication date: 13 November 2012

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Gaussian processes (60G15) Voting theory (91B12) Social choice (91B14) Exchangeability for stochastic processes (60G09)

Related Items

Standard simplices and pluralities are not the most noise stable, Compactness and Rigidity of λ-Surfaces, Probabilistic view of voting, paradoxes, and manipulation, Low correlation noise stability of symmetric sets, Nonlocal Games with Noisy Maximally Entangled States are Decidable, The probability of intransitivity in dice and close elections, A two-sided estimate for the Gaussian noise stability deficit, Three candidate plurality is stablest for small correlations, Robust optimality of Gaussian noise stability, Dimension Reduction for Polynomials over Gaussian Space and Applications, The structure of Gaussian minimal bubbles, Gaussian bounds for noise correlation of resilient functions, The Gaussian double-bubble and multi-bubble conjectures, Remarks on Gaussian Noise Stability, Brascamp-Lieb and Slepian Inequalities, Unnamed Item, Common Information, Noise Stability, and Their Extensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Noise stability of functions with low influences: invariance and optimality
• Proof of the double bubble conjecture
• Sharp inequalities for functional integrals and traces of conformally invariant operators.
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• Gaussian bounds for noise correlation of functions
• On the hardness of approximating Multicut and Sparsest-Cut
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Conditional hardness for approximate coloring
• Towards Sharp Inapproximability for Any 2-CSP
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• On the power of unique 2-prover 1-round games
• Limit Theorems for Multilinear Forms and Quasipolynomial Functions
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Coin flipping from a cosmic source: On error correction of truly random bits
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Social Indeterminacy
• Comparison theorems for exit times