Binary perceptron computational gap – a parametric fl RDT view

Mihailo Stojnic · 2025

Read Binary perceptron computational gap – a parametric fl RDT view by Mihailo Stojnic (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01037.txt.

Description

Mihailo Stojnic analyzes the asymmetric binary perceptron, a simple neural network model used as a storage memory, through the lens of fully lifted random duality theory. The model is believed to show a statistical computational gap: below one density of stored patterns, suitable weights exist, but finding them efficiently may only be possible below a lower density.

Stojnic applies a parametric form of the duality theory and tracks how its key sequence behaves across lifting levels. The behavior changes character after the second level, which he connects to the gap between the two thresholds. Numerical values at the second level give a critical density estimate, and by the fifth level the estimate settles lower, which he reads as satisfactory convergence toward the satisfiability threshold.

Catalog record

CREATORMihailo Stojnic
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01037

Browse the full library · About the Tower of Babel