{"id":9783,"date":"2026-01-16T07:02:31","date_gmt":"2026-01-16T07:02:31","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2026\/01\/16\/2601-10628\/"},"modified":"2026-01-16T07:02:31","modified_gmt":"2026-01-16T07:02:31","slug":"2601-10628","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2026\/01\/16\/2601-10628\/","title":{"rendered":"Parametric RDT approach to computational gap of symmetric binary perceptron"},"content":{"rendered":"<p>    Parametric RDT approach to computational gap of symmetric binary perceptron<br \/>\n \t<BR><br \/>\n<BR><\/BR><br \/>\n    <!-- no image --><br \/>\n \t<BR><br \/>\n<BR><\/BR><\/p>\n<div>arXiv:2601.10628v1 Announce Type: new<br \/>\nAbstract: 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} ($alpha_c$) &#8212; emph{algorithmic} ($alpha_a$) constraints density threshold change thereby suggesting a potential existence of a nonzero computational gap $SCG=alpha_c-alpha_a$. The second level estimate is shown to match the theoretical $alpha_c$ whereas the $rrightarrow infty$ level one is proposed to correspond to $alpha_a$. For example, for the canonical SBP ($kappa=1$ margin) we obtain $alpha_capprox 1.8159$ on the second and $alpha_aapprox 1.6021$ (with converging tendency towards $sim 1.59$ range) on the seventh level. Our propositions remarkably well concur with recent literature: (i) in [20] local entropy replica approach predicts $alpha_{LE}approx 1.58$ as the onset of clustering defragmentation (presumed driving force behind locally improving algorithms failures); (ii) in $alpharightarrow 0$ regime we obtain on the third lifting level $kappaapprox 1.2385sqrt{frac{alpha_a}{-logleft ( alpha_a right ) }}$ which qualitatively matches overlap gap property (OGP) based predictions of [43] and identically matches local entropy based predictions of [24]; (iii) $c$-sequence ordering change phenomenology mirrors the one observed in asymmetric binary perceptron (ABP) in [98] and the negative Hopfield model in [100]; and (iv) as in [98,100], we here design a CLuP based algorithm whose practical performance closely matches proposed theoretical predictions.<\/div>\n<p> \t<BR><br \/>\n <BR><\/BR><br \/>\n    Mihailo Stojnic<br \/>\n \t<BR><br \/>\n<BR><\/BR><br \/>\n<a href=\"https:\/\/arxiv.org\/abs\/2601.10628\">Go to original source<\/a><br \/>\n \t<BR><br \/>\n <BR><\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Parametric RDT approach to computational gap of symmetric binary perceptron arXiv:2601.10628v1 Announce Type: new Abstract: 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 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,1878,414,113,415,420,112],"tags":[4620,161,788],"class_list":["post-9783","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cond-mat-dis-nn","category-cs-it","category-cs-lg","category-math-it","category-math-pr","category-stat-ml","tag-alpha","tag-level","tag-parametric"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/9783"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=9783"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/9783\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=9783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=9783"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=9783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}