OpenAlex ·
Strong freezing in binary perceptron models
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.06275
- Original
- Read it at the publisher
- Topics
Abstract
The binary perceptron model concerns the set of solutions obtained by intersecting random half-spaces. One of the most striking physics predictions for this model, going back to Krauth and Mézard [KM89] and sharpened in [HWK13, HK14], is strong freezing: typical solutions are at Hamming distance of order $n$ from every other solution. This phenomenon has attracted a lot of attention over the years, partly because of its intricate connections to statistical physics and computational complexity. We prove strong freezing at every positive constraint density for a general class of perceptron models and for any disorder with independent entries of mean zero and unit variance. More precisely, with probability at least $1-e^{-c\sqrt n}$, all but an $e^{-c\sqrt n}$ fraction of the solutions have no other solution within Hamming distance $δn$. In particular, our result includes the asymmetric binary perceptron at every margin, for which strong freezing has been a long-standing open problem [KM89,HWK13,HK14], and the symmetric binary perceptron, for which we recover the strong freezing results of Perkins and Xu [PX24] and of Abbe, Li and Sly [ALS21]. Our proof crucially relies on replacing the number of constraints by a Poisson variable, which makes the numbers of constraints cutting out different subsets of the hypercube independent. Since each constraint can only remove solutions, the FKG inequality then decouples the partition function from the event that two nearby configurations are both solutions.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
Defect-limited thermal transport in AlN using pretrained machine-learning interatomic potentials
Peeling off Abelian Anyons and Proliferation Transitions
Interfacial Charge Transfer and Morphology Govern Magnetism in Ultrathin VOx/MoSe2 Heterostructures
Complete Magnetic Hierarchy in Bichromatically Driven Unconventional Magnets
Exchange self-energy and vertex corrections to static screening in the two-dimensional electron gas
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.