Plurality is stablest conjecture, discrete version
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.