The Majority is Least Stable conjecture for linear threshold functions

Let f ⁣:{1,1}n{1,1}f\colon\{-1,1\}^{n}\rightarrow\{-1,1\} be a linear threshold function, with nn odd. For ρ[0,1]\rho\in[0,1], let Stabρ[f]\operatorname{Stab}_{\rho}[f] denote the noise stability of ff at correlation ρ\rho, and let Majn\operatorname{Maj}_{n} be the majority function on nn variables. Majority is Least Stable conjecture. For all ρ[0,1]\rho\in[0,1],

Stabρ[f]Stabρ[Majn].\operatorname{Stab}_{\rho}[f]\geq\operatorname{Stab}_{\rho}[\operatorname{Maj}_{n}].

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.