Plurality Is Asymptotically Stablest conjecture

From papers

Let 0ρ10\leq\rho\leq1 and let q2q\geq2 be an integer. For f:[q]n[0,1]f:[q]^n\to[0,1], let Sρ(f)\mathbb{S}_\rho(f) denote its noise stability and let Infi(f)\mathrm{Inf}_i(f) denote the influence of coordinate ii. Plurality Is Asymptotically Stablest conjecture. For every ϵ>0\epsilon>0 there exists τ>0\tau>0 such that, if E[f]=1/q{\bf E}[f]=1/q and Infi(f)τ\mathrm{Inf}_i(f)\leq\tau for all ii, then

Sρ(f)q2/(1+ρ)+o(1)+ϵ,\mathbb{S}_\rho(f)\leq q^{-2/(1+\rho)+o(1)}+\epsilon,

where o(1)o(1) tends to 00 as qq\to\infty, independently of ϵ\epsilon and τ\tau. This is an asymptotic stability conjecture for low-influence functions on the qq-ary cube, motivated by optimal approximation results. The source does not state a resolution.

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

Elchanan Mossel, Ryan O'Donnell and Krzysztof Oleszkiewicz, “Noise stability of functions with low influences: invariance and optimality”, arXiv:math/0503503 (2005).

Solutions 0

No solutions have been posted yet.