Plurality is Stablest conjecture for candidates
Plurality is Stablest conjecture for candidates
For , let , where is the probability simplex, and let denote the influence of coordinate on the th coordinate function. Define the noise stability by , and let be the plurality function, with ties mapped to the uniform vector . For every and , there is such that the following holds for every satisfying for all and .
Plurality is Stablest conjecture. If and , then
If , then
This is the formal discrete Plurality is Stablest statement cited as the source of the three-candidate conjecture and as the conjectural ingredient for sharp MAX--CUT hardness. The surrounding text notes that the three-candidate case is proved only for the narrower range , while the conjecture is expected for the stated range; the notation retains the source's parameter .
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, “Three Candidate Plurality is Stablest for Correlations at most 1/10”, arXiv:2306.03312 (2023).
Additional references
2 papers in this index state this conjecture (2012–2023). The statement above is taken from the most recent of them; the others are arXiv:1211.7138.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.