OpenFrontiers
Join
← Back to the index
OP-2980OpenProbability

Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry · 2010-prob-195

Combinatorial probability · ICM 2010: Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry

MSC 60 · Probability theory and stochastic processes

Inferred from the community field; finer classification has not been reviewed.

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

For an integer k≥3k\ge 3, write [k]={1,…,k}[k]=\{1,\ldots,k\}. Given n≥1n\ge 1 and ρ∈[0,1]\rho\in[0,1], let X=(X1,…,Xn)X=(X_1,\ldots,X_n) be uniformly distributed on [k]n[k]^n, and, conditionally on XX, construct Y=(Y1,…,Yn)Y=(Y_1,\ldots,Y_n) by independently setting, for each ii, Yi=XiY_i=X_i with probability ρ\rho and otherwise resampling YiY_i uniformly from [k][k]. For a function f:[k]n→[k]f:[k]^n\to[k], define its noise stability by

Sρ(f)=Pr⁡[f(X)=f(Y)].S_\rho(f)=\Pr[f(X)=f(Y)].

Call ff balanced if Pr⁡[f(X)=j]=1/k\Pr[f(X)=j]=1/k for every j∈[k]j\in[k]. If X(i)X^{(i)} is obtained from XX by independently resampling its iith coordinate uniformly from [k][k], define the influence of coordinate ii by

Inf⁡i(f)=Pr⁡[f(X)≠f(X(i))].\operatorname{Inf}_i(f)=\Pr[f(X)\ne f(X^{(i)})].

For m≥1m\ge 1, let Plur⁡k,m:[k]m→[k]\operatorname{Plur}_{k,m}:[k]^m\to[k] output a label occurring most often in its input, using any fixed rule to break ties, and set

PlurStab⁡(k,ρ)=lim⁡m→∞Sρ(Plur⁡k,m),\operatorname{PlurStab}(k,\rho)=\lim_{m\to\infty}S_\rho(\operatorname{Plur}_{k,m}),

where the value of the limit is independent of the tie-breaking rule. Prove that for every integer k≥3k\ge 3, every ρ∈[0,1]\rho\in[0,1], and every ε>0\varepsilon>0, there exists τ>0\tau>0 such that, for every n≥1n\ge 1 and every balanced function f:[k]n→[k]f:[k]^n\to[k] satisfying Inf⁡i(f)≤τ\operatorname{Inf}_i(f)\le\tau for all i∈{1,…,n}i\in\{1,\ldots,n\},

Sρ(f)≤PlurStab⁡(k,ρ)+ε.S_\rho(f)\le \operatorname{PlurStab}(k,\rho)+\varepsilon.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗
Remaining questions in this record

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

Let [3]={1,2,3}[3]=\{1,2,3\}. Given n≥1n\ge 1 and ρ∈[0,1]\rho\in[0,1], let X=(X1,…,Xn)X=(X_1,\ldots,X_n) be uniformly distributed on [3]n[3]^n, and, conditionally on XX, construct Y=(Y1,…,Yn)Y=(Y_1,\ldots,Y_n) by independently setting, for each ii, Yi=XiY_i=X_i with probability ρ\rho and otherwise resampling YiY_i uniformly from [3][3]. For a function f:[3]n→[3]f:[3]^n\to[3], define

Sρ(f)=Pr⁡[f(X)=f(Y)].S_\rho(f)=\Pr[f(X)=f(Y)].

Call ff balanced if Pr⁡[f(X)=j]=1/3\Pr[f(X)=j]=1/3 for every j∈[3]j\in[3]. If X(i)X^{(i)} is obtained from XX by independently resampling its iith coordinate uniformly from [3][3], define

Inf⁡i(f)=Pr⁡[f(X)≠f(X(i))].\operatorname{Inf}_i(f)=\Pr[f(X)\ne f(X^{(i)})].

For m≥1m\ge 1, let Plur⁡3,m:[3]m→[3]\operatorname{Plur}_{3,m}:[3]^m\to[3] output a label occurring most often in its input, using any fixed rule to break ties, and set

PlurStab⁡(3,ρ)=lim⁡m→∞Sρ(Plur⁡3,m),\operatorname{PlurStab}(3,\rho)=\lim_{m\to\infty}S_\rho(\operatorname{Plur}_{3,m}),

where the limit is independent of the tie-breaking rule. Prove that for every ρ∈[0,1]\rho\in[0,1] and every ε>0\varepsilon>0, there exists τ>0\tau>0 such that, for every n≥1n\ge 1 and every balanced function f:[3]n→[3]f:[3]^n\to[3] satisfying Inf⁡i(f)≤τ\operatorname{Inf}_i(f)\le\tau for all i∈{1,…,n}i\in\{1,\ldots,n\},

Sρ(f)≤PlurStab⁡(3,ρ)+ε.S_\rho(f)\le \operatorname{PlurStab}(3,\rho)+\varepsilon.

Source reference: Steven Heilman, “Three Candidate Plurality is Stablest for Correlations at most 1/10,” preprint, 2023, Theorem 1.6 (three-candidate Plurality is Stablest Conjecture), arXiv:2306.03312, https://arxiv.org/abs/2306.03312.

Progress & source assessment

Source-reported assessment from the ICM catalogue snapshot. This is not an independent review by Frontier Science.

The statement is the balanced, positive-correlation Plurality is Stablest Conjecture. It remains unresolved. The cases ρ=0\rho=0 and ρ=1\rho=1 are immediate, and substantial special cases are known, but no result covers every fixed ρ∈(0,1)\rho\in(0,1) even for k=3k=3, nor every k≥4k\ge 4.

  • Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell, “Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?”, SIAM Journal on Computing 37(1), 2007, 319–357, DOI 10.1137/S0097539705447372. This paper introduced Plurality is Stablest and explicitly left it open.
  • Marcus Isaksson and Elchanan Mossel, “Maximally Stable Gaussian Partitions with Discrete Applications,” Israel Journal of Mathematics 189, 2012, 347–396, DOI 10.1007/s11856-011-0181-7, arXiv:0903.3362. Conjecture 1.9 gives the formal discrete conjecture; Theorems 1.10 and 1.11 relate it to the equal-measure Standard Simplex Conjecture in Gaussian space. Thus the Gaussian conjecture would imply the statement, but it is not itself proved there.
  • Steven Heilman, “Stable Gaussian Minimal Bubbles,” preprint, 2019, arXiv:1901.03934. Corollary 1.11 proves a weak stability estimate near the limiting regime ρ→1−\rho\to1^{-} (unconditionally for three parts and conditionally in the stated higher-part setting). Its error term does not give the sharp inequality required here for every fixed ρ\rho.
  • Steven Heilman and Alex Tarter, “Three Candidate Plurality is Stablest for Small Correlations,” Forum of Mathematics, Sigma 9 (2021), e65, DOI 10.1017/fms.2021.56, arXiv:2011.05583. They prove the conjecture for k=3k=3 and all sufficiently small fixed positive correlations, the first fixed-ρ\rho case.
  • Steven Heilman, “Three Candidate Plurality is Stablest for Correlations at most 1/10,” preprint, 2023, arXiv:2306.03312. Theorems 1.5 and 1.6 prove the three-candidate Gaussian and discrete assertions for positive correlations through ρ=0.1082\rho=0.1082 (and also a negative-correlation analogue on a small interval). The paper explicitly states that the three-candidate result should hold for all ρ<1\rho<1 and identifies extending the estimates to all correlations as a remaining bottleneck.

Consequently, the strongest direct progress still leaves positive correlations above the proved three-candidate range and the general k≥4k\ge4 case open, so it does not resolve the quantified assertion in the statement.

References
  1. [1]ICM Conjectures · 2010-prob-195 link
  2. [2]ICM 2010: Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.