Plurality is stablest conjecture, discrete version

From papers

Let m2m\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 Infi(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 PLURm,n\operatorname{PLUR}_{m,n} be the plurality function, with ties mapped to m1i=1meim^{-1}\sum_{i=1}^m e_i. Plurality is stablest conjecture, discrete version. There exists τ>0\tau>0 such that, whenever Infi(fj)τ\operatorname{Inf}_i(f_j)\leq\tau for every i,ji,j and Ef=m1i=1mei\mathbb{E}f=m^{-1}\sum_{i=1}^m e_i,

SρflimnSρPLURm,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.

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

No solutions have been posted yet.