{"id":"arxiv/2601.10628","url":"https://arxiv.org/abs/2601.10628","tags":["stat.ML","cond-mat.dis-nn","cs.IT","cs.LG","math.PR"],"score":0,"title":"Parametric RDT approach to computational gap of symmetric binary perceptron","domain":"stat.ML","source":"arxiv","authors":["Mihailo Stojnic"],"reviews":0,"subject":"stat.ML","summary":"We study potential presence of statistical-computational gaps (SCG) in symmetric binary perceptrons (SBP) via a parametric utilization of \\emph{fully lifted random duality theory} (fl-RDT) [96]. A structural change from decreasingly to arbitrarily ordered $c$-sequence (a key fl-RDT parametric component) is observed on the second lifting level and associated with \\emph{satisfiability} ($α_c$) -- \\emph{algorithmic} ($α_a$) constraints density threshold change thereby suggesting a potential existence of a nonzero computational gap $SCG=α_c-α_a$. The second level estimate is shown to match the…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-01-15","reactions":{}}