# Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT arXiv: https://arxiv.org/abs/2506.19276 · HTML: https://mlsanity.com/paper/2506.19276/ ## Key facts - Cited by 5 papers in the map (data through 14 Oct 2026). - Builds on 35 of its 109 references that are in the map. - First posted on arXiv 24 Jun 2025. ## Builds on (most cited first, 30 of 35) - [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022) - [Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses](https://mlsanity.com/paper/1509.05753/) (2015) - [Unveiling the structure of wide flat minima in neural networks](https://mlsanity.com/paper/2107.01163/) (2021) - [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013) - [Another look at the Gardner problem](https://mlsanity.com/paper/1306.3979/) (2013) - [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013) - [Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations](https://mlsanity.com/paper/1907.07578/) (2019) - [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020) - [Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems](https://mlsanity.com/paper/1511.05634/) (2015) - [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018) - [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021) - [Fully lifted random duality theory](https://mlsanity.com/paper/2312.00070/) (2023) - [Origin of the computational hardness for learning with binary synapses](https://mlsanity.com/paper/1408.1784/) (2014) - [Optimal Low-Degree Hardness of Maximum Independent Set](https://mlsanity.com/paper/2010.06563/) (2020) - [Discrete perceptrons](https://mlsanity.com/paper/1306.4375/) (2013) - [Lifting ℓ1-optimization strong and sectional thresholds](https://mlsanity.com/paper/1306.3770/) (2013) - [Lifting/lowering Hopfield models ground state energies](https://mlsanity.com/paper/1306.3975/) (2013) - [Algorithmic pure states for the negative spherical perceptron](https://mlsanity.com/paper/2010.15811/) (2020) - [Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster](https://mlsanity.com/paper/2111.03084/) (2021) - [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023) - [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023) - [Clustering of solutions in the symmetric binary perceptron](https://mlsanity.com/paper/1911.06756/) (2019) - [Algorithms and Barriers in the Symmetric Binary Perceptron Model](https://mlsanity.com/paper/2203.15667/) (2022) - [Spherical perceptron as a storage memory with limited errors](https://mlsanity.com/paper/1306.3809/) (2013) - [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023) - [Entropy landscape of solutions in the binary perceptron problem](https://mlsanity.com/paper/1304.2850/) (2013) - [Local algorithms for independent sets are half-optimal](https://mlsanity.com/paper/1402.0485/) (2014) - [On-Line Balancing of Random Inputs](https://mlsanity.com/paper/1903.06898/) (2019) - [Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses](https://mlsanity.com/paper/2110.07847/) (2021) - [Hardness of sampling solutions from the Symmetric Binary Perceptron](https://mlsanity.com/paper/2407.16627/) (2024) ## Built on by (most cited first, 5 of 5) - [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025) - [CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energy](https://mlsanity.com/paper/2507.22396/) (2025) - [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025) - [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026) - [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026) ## Abstract (arXiv) We study classical asymmetric binary perceptron (ABP) and associated local entropy (LE) as potential source of its algorithmic hardness. Isolation of typical ABP solutions in SAT phase seemingly suggests a universal algorithmic hardness. Paradoxically, efficient algorithms do exist even for constraint densities α fairly close but at a finite distance (computational gap) from the capacity. In recent years, existence of rare large dense clusters and magical ability of fast algorithms to find them have been posited as the conceptual resolution of this paradox. Monotonicity or breakdown of the LEs associated with such atypical clusters are predicated to play a key role in their thinning-out or even complete defragmentation. Invention of fully lifted random duality theory (fl RDT) [90,93,94] allows studying random structures typical features. A large deviation upgrade, sfl LD RDT [96,97], moves things further and enables atypical features characterizations as well. Utilizing the machinery of [96,97] we here develop a generic framework to study LE as an ABP's atypical feature. Already on the second level of lifting we discover that the LE results are closely matching those obtained through replica methods. For classical zero threshold ABP, we obtain that LE breaks down for α in (0.77,0.78) interval which basically matches α~ 0.75-0.77 range that currently best ABP solvers can handle and effectively indicates that LE's behavior might indeed be among key reflections of the ABP's computational gaps presumable existence.