SBP algorithmic threshold conjecture

Let G\ninRm×nG\nin\mathbb{R}^{m\times n} have independent standard-normal entries. For constraint density α=limnm/n\alpha=\lim_{n\to\infty}m/n and κR+\kappa\in\mathbb{R}_+, consider the statistical SBP S(G,κ,α)\mathbf{\mathcal S}(G,\kappa,\alpha). Define its algorithmic threshold by

αa(κ)=max{α | limnP(S(G,κ,α) is solvable in polynomial time)=1}.\alpha_a(\kappa)=\max\left\{\alpha\ \middle|\ \lim_{n\to\infty}\mathbb{P}\bigl(\mathbf{\mathcal S}(G,\kappa,\alpha)\text{ is solvable in polynomial time}\bigr)=1\right\}.

Let ψˉrd(r)=ψˉrd\bar{\psi}_{rd}^{(r)}=\bar{\psi}_{rd}, with ψˉrd\bar{\psi}_{rd} and p^,q^,c^,γ^sq\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c},\hat{\gamma}_{sq} as in the cited definitions and theorem. SBP algorithmic threshold conjecture. There is a non-increasing convergent sequence αc(r)(κ)\alpha_c^{(r)}(\kappa) defined by

αc(r)(κ)={α | ψˉrd(r)(p^,q^,c^,γ^sq)=0},\alpha_c^{(r)}(\kappa)=\left\{\alpha\ \middle|\ \bar{\psi}_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c},\hat{\gamma}_{sq})=0\right\},

such that

αc(r)(κ)αa(κ),limrαc(r)(κ)=α^a(κ)=αa(κ).\alpha_c^{(r)}(\kappa)\geq\alpha_a(\kappa),\qquad \lim_{r\to\infty}\alpha_c^{(r)}(\kappa)=\hat{\alpha}_a(\kappa)=\alpha_a(\kappa).

Since αc(κ)=αc(2)(κ)\alpha_c(\kappa)=\alpha_c^{(2)}(\kappa), the statistical computational gap is

SCG=αc(κ)αa(κ)=αc(2)(κ)limrαc(r)(κ).SCG=\alpha_c(\kappa)-\alpha_a(\kappa)=\alpha_c^{(2)}(\kappa)-\lim_{r\to\infty}\alpha_c^{(r)}(\kappa).

The claim proposes that the fl-RDT hierarchy converges to the SBP algorithmic threshold, with the finite-rr quantities providing upper estimates; the source gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Mihailo Stojnic, “Parametric RDT approach to computational gap of symmetric binary perceptron”, arXiv:2601.10628 (2026).

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.