Parametric fl-RDT algorithmic conjecture

Less than 1 year old · traced to

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 | lim⁡n→∞P(ψ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=lim⁡r→∞ψ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=lim⁡r→∞ψ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,lim⁡r→∞ψ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=lim⁡r→∞ψrd(r)(p^,q^,c^>)−lim⁡r→∞ψ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.

References

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.