The Majority is Least Stable conjecture for linear threshold functions

About 9 years old · traced to

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 Maj⁡n\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⁡ρ[Maj⁡n].\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.

References

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.