Plurality is stablest conjecture, discrete version

About 7 years old · traced to

Let m≥2m\geq 2, let ρ∈[0,1]\rho\in[0,1], and let ε>0\varepsilon>0. For a function f:{1,…,m}n→Δmf:\{1,\ldots,m\}^n\to\Delta_m, write Inf⁡i(fj)\operatorname{Inf}_i(f_j) for the influence of coordinate ii on component fjf_j, and let SρfS_\rho f denote its total noise stability. Let e1,…,eme_1,\ldots,e_m be the standard basis vectors and let PLUR⁡m,n\operatorname{PLUR}_{m,n} be the plurality function, with ties mapped to m−1∑i=1meim^{-1}\sum_{i=1}^m e_i. Plurality is stablest conjecture, discrete version. There exists τ>0\tau>0 such that, whenever Inf⁡i(fj)≤τ\operatorname{Inf}_i(f_j)\leq\tau for every i,ji,j and Ef=m−1∑i=1mei\mathbb{E}f=m^{-1}\sum_{i=1}^m e_i,

Sρf≤lim⁡n→∞SρPLUR⁡m,n+ε.S_\rho f\leq\lim_{n\to\infty}S_\rho\operatorname{PLUR}_{m,n}+\varepsilon.

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

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.