SBP algorithmic threshold conjecture
SBP algorithmic threshold conjecture
Let have independent standard-normal entries. For constraint density and , consider the statistical SBP . Define its algorithmic threshold by
Let , with and as in the cited definitions and theorem. SBP algorithmic threshold conjecture. There is a non-increasing convergent sequence defined by
such that
Since , the statistical computational gap is
The claim proposes that the fl-RDT hierarchy converges to the SBP algorithmic threshold, with the finite- 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.