Capacity threshold for the Ising perceptron

2024/04/29 by Brice Huang, Huang, Brice · 9 citations
Computer Science · #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Neural Networks and Applications #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2404.18902

openalex publication_date 2024/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the capacity of the Ising perceptron is with high probability upper bounded by the constant α_⋆ ≈ 0.833 conjectured by Krauth and Mézard, under the condition that an explicit two-variable function \mathscrS_*(λ₁,λ₂) is maximized at (1,0). The earlier work of Ding and Sun proves the matching lower bound subject to a similar numerical condition, and together these results give a conditional proof of the conjecture of Krauth and Mézard.

Cited by

• Uniqueness of Replica-symmetric Saddle Point for Ising Perceptron
• Binary perceptron computational gap -- a parametric fl RDT view
• Are Neural Networks Collision Resistant?
• A CLuP algorithm to practically achieve ∼ 0.76 SK--model ground state free energy
• Proof of The TAP Free Energy for High-Dimensional Linear Regression with Spherical Priors at All Temperatures
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• A large deviation view of stationarized fully lifted blirp interpolation
• Overlap Gap and Computational Thresholds in the Square Wave Perceptron
• Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems

Related

• Capacity lower bound for the Ising perceptron
• A note on the capacity of the binary perceptron
• Gardner formula for Ising perceptron models at small densities
• Sharp threshold sequence and universality for Ising perceptron models
• Sharp threshold for the Ising perceptron model