The Majority is Least Stable conjecture for linear threshold functions
The Majority is Least Stable conjecture for linear threshold functions
Let be a linear threshold function, with odd. For , let denote the noise stability of at correlation , and let be the majority function on variables. Majority is Least Stable conjecture. For all ,
This conjecture was proposed by Benjamini, Kalai, and Schramm and presented by Filmus et al. as an open problem. The paper's title and accompanying remark indicate that the conjecture as stated is false; independent counterexamples were observed by Sivakanth Gopi, and by Steven Heilman and Daniel Kane.
Sources & referencesView supporting material
Primary source
Vishesh Jain, “A Counterexample to the "Majority is Least Stable" Conjecture”, arXiv:1703.07657 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.