Plurality is stablest conjecture, discrete version
Let , let , and let . For a function , write for the influence of coordinate on component , and let denote its total noise stability. Let be the standard basis vectors and let be the plurality function, with ties mapped to . Plurality is stablest conjecture, discrete version. There exists such that, whenever for every and ,
This is the formal low-influence, equal-outcome-probability version of the voting claim and would identify plurality as asymptotically optimal for noise stability; it remains open in the full stated range.
References
Primary source
Steven Heilman, “Hyperstable Sets with Voting and Algorithmic Hardness Applications”, arXiv:2209.11216 (2022).
Additional references
4 papers in this index state this conjecture (2019–2022). The statement above is taken from the most recent of them; the others are arXiv:2011.05583, arXiv:2006.05460, arXiv:1901.03934.
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
No solutions have been posted yet.