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
| CREATOR | Mihailo Stojnic |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-01037