Parametric fl-RDT algorithmic conjecture

Assume the setup of the paper's fl-RDT theorem, including the quantities ψrp\psi_{rp}, ψrd\psi_{rd}, p^\hat{\mathbf p}, q^\hat{\mathbf q}, and c^\hat{\mathbf c}. Define the algorithmically achievable value ψrp,a\psi_{rp,a} by

ψrp,a=max{ψrp | limnP(ψrp can be achieved in polynomial time)=1}.\psi_{rp,a}=\max\left\{\psi_{rp}\ \middle|\ \lim_{n\to\infty}\mathbb{P}(\psi_{rp}\text{ can be achieved in polynomial time})=1\right\}.

Let ψrd(r)=ψrd\psi_{rd}^{(r)}=\psi_{rd}, with ψrd\psi_{rd} as in the stated fl-RDT theorem. Parametric fl-RDT algorithmic conjecture. There is an rr-sequence ψrd(r)\psi_{rd}^{(r)} with a decreasing sequence c^>\hat{\mathbf c}^{>} such that

ψrp=limrψrd(r)(p^,q^,c^>).\psi_{rp}=\lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{>} ).

If no subinterval of [0,1][0,1] contains no elements of p^\hat{\mathbf p} and q^\hat{\mathbf q}, then

ψrp=limrψrd(r)(p^,q^,c^>)=ψrp,a,SCG=ψrpψrp,a=0.\psi_{rp}=\lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{>} )=\psi_{rp,a},\qquad SCG=\psi_{rp}-\psi_{rp,a}=0.

Otherwise, there is an rr-sequence with an arbitrarily ordered sequence c^\hat{\mathbf c}^{\sim} such that

ψrd(r)(p^,q^,c^)ψrp,a,limrψrd(r)(p^,q^,c^)=ψ^rd=ψrp,a,\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{\sim})\geq\psi_{rp,a},\qquad \lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{\sim})=\hat{\psi}_{rd}=\psi_{rp,a},

and

SCG=ψrpψrp,a=limrψrd(r)(p^,q^,c^>)limrψrd(r)(p^,q^,c^).SCG=\psi_{rp}-\psi_{rp,a}=\lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{>} )-\lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{\sim} ).

The conjecture proposes a general parametric fl-RDT mechanism relating computationally achievable values to limiting finite-parameter predictions; the source provides no resolution, so it 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.