{"ID":2847087,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.01037","arxiv_id":"2511.01037","title":"Binary perceptron computational gap -- a parametric fl RDT view","abstract":"Recent studies suggest that asymmetric binary perceptron (ABP) likely exhibits the so-called statistical-computational gap characterized with the appearance of two phase transitioning constraint density thresholds: \\textbf{\\emph{(i)}} the \\emph{satisfiability threshold} $α_c$, below/above which ABP succeeds/fails to operate as a storage memory; and \\textbf{\\emph{(ii)}} \\emph{algorithmic threshold} $α_a$, below/above which one can/cannot efficiently determine ABP's weight so that it operates as a storage memory. We consider a particular parametric utilization of \\emph{fully lifted random duality theory} (fl RDT) [85] and study its potential ABP's algorithmic implications. A remarkable structural parametric change is uncovered as one progresses through fl RDT lifting levels. On the first two levels, the so-called $\\c$ sequence -- a key parametric fl RDT component -- is of the (natural) decreasing type. A change of such phenomenology on higher levels is then connected to the $α_c$ -- $α_a$ threshold change. Namely, on the second level concrete numerical values give for the critical constraint density $α=α_c\\approx 0.8331$. While progressing through higher levels decreases this estimate, already on the fifth level we observe a satisfactory level of convergence and obtain $α\\approx 0.7764$. This allows to draw two striking parallels: \\textbf{\\emph{(i)}} the obtained constraint density estimate is in a remarkable agrement with range $α\\in (0.77,0.78)$ of clustering defragmentation (believed to be responsible for failure of locally improving algorithms) [17,88]; and \\textbf{\\emph{(ii)}} the observed change of $\\c$ sequence phenomenology closely matches the one of the negative Hopfield model for which the existence of efficient algorithms that closely approach similar type of threshold has been demonstrated recently [87].","short_abstract":"Recent studies suggest that asymmetric binary perceptron (ABP) likely exhibits the so-called statistical-computational gap characterized with the appearance of two phase transitioning constraint density thresholds: \\textbf{\\emph{(i)}} the \\emph{satisfiability threshold} $α_c$, below/above which ABP succeeds/fails to op...","url_abs":"https://arxiv.org/abs/2511.01037","url_pdf":"https://arxiv.org/pdf/2511.01037v1","authors":"[\"Mihailo Stojnic\"]","published":"2025-11-02T18:23:49Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cond-mat.dis-nn\",\"cs.IT\",\"cs.LG\",\"math.PR\"]","methods":"[]","has_code":false}