On The "Majority is Least Stable" Conjecture

2022/02/18 by Aniruddha Biswas, Palash Sarkar, Biswas, Aniruddha +1 · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Graph theory and applications #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2202.09024

Abstract

We show that the "majority is least stable" conjecture is true for n=1 and 3 and false for all odd n≥ 5.

Cited by

• Counterexample to majority optimality in NICD with erasures

Related

• A Counterexample to the "Majority is Least Stable" Conjecture
• Majority is Stablest : Discrete and SoS
• Standard Simplices and Pluralities are Not the Most Noise Stable
• Noise Stability of Weighted Majority
• Three Candidate Plurality is Stablest for Correlations at most 1/10