Let G\ninRm×n have independent standard-normal entries. For constraint density α=limn→∞m/n and κ∈R+, consider the statistical SBP S(G,κ,α). Define its algorithmic threshold by
αa(κ)=max{αn→∞limP(S(G,κ,α) is solvable in polynomial time)=1}.
Let ψˉrd(r)=ψˉrd, with ψˉrd and p^,q^,c^,γ^sq as in the cited definitions and theorem. SBP algorithmic threshold conjecture. There is a non-increasing convergent sequence αc(r)(κ) defined by
αc(r)(κ)={αψˉrd(r)(p^,q^,c^,γ^sq)=0},
such that
αc(r)(κ)≥αa(κ),r→∞limαc(r)(κ)=α^a(κ)=αa(κ).
Since αc(κ)=αc(2)(κ), the statistical computational gap is
SCG=αc(κ)−αa(κ)=αc(2)(κ)−r→∞limαc(r)(κ).
The claim proposes that the fl-RDT hierarchy converges to the SBP algorithmic threshold, with the finite-r quantities providing upper estimates; the source gives no resolution, so the conjecture remains open.
References
Primary source
Mihailo Stojnic, “Parametric RDT approach to computational gap of symmetric binary perceptron”, arXiv:2601.10628 (2026).