pith. sign in

arxiv: 2505.20954 · v4 · submitted 2025-05-27 · ❄️ cond-mat.dis-nn · cond-mat.stat-mech

Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems

Damien Barbier This is my paper

Pith reviewed 2026-05-19 13:35 UTC · model grok-4.3

classification ❄️ cond-mat.dis-nn cond-mat.stat-mech
keywords constraint satisfaction problemsconnected solutionssymmetric binary perceptronlocal entropy biasstatistical mechanics ensemblephase transitionslocal algorithmssolution manifolds
0
0 comments X

The pith

A new statistical mechanics ensemble reveals a stable cluster of connected solutions in the symmetric binary perceptron that persists up to a critical threshold.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a statistical mechanics ensemble built on local entropy bias to characterize connected solutions in constraint satisfaction problems where most solutions are isolated. Applied to the symmetric binary perceptron, the ensemble identifies a cluster of delocalized connected solutions. This cluster remains stable until a critical threshold that depends on constraint density, at which point solution paths shatter. The transition accounts for the range where local algorithms still succeed even though typical solutions are isolated. Modified Monte Carlo simulations targeting these solutions match the predicted stability limit.

Core claim

The authors introduce an ensemble that uses local entropy bias to measure the manifold of connected solutions in CSPs. In the symmetric binary perceptron this ensemble detects a cluster of delocalized connected solutions whose local stability holds up to a threshold κ^{no-mem}_{loc. stab.} that depends on the constraint density α. Past this point the paths connecting solutions break apart, a phenomenon missed by standard statistical mechanics treatments of the model. The same threshold marks the point where local search algorithms cease to find solutions, and this prediction is confirmed by a custom Monte Carlo procedure that preferentially samples the connected manifold.

What carries the argument

The local entropy bias ensemble, which reweights the measure on solutions to favor those with high local entropy and thereby exposes the manifold of connected solutions.

If this is right

  • Local algorithms locate solutions in the symmetric binary perceptron for all thresholds below the stability limit.
  • Solution paths shatter exactly at the critical threshold, marking a transition in landscape connectivity.
  • Conventional statistical mechanics ensembles overlook the connected cluster because they do not bias toward local entropy.
  • The ensemble supplies a concrete diagnostic for hardness transitions in other CSPs dominated by isolated solutions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same bias construction may identify usable connected components in other models where isolated minima dominate the typical landscape.
  • Algorithmic success ranges could be predicted by computing the local stability threshold rather than by exhaustive search.
  • The approach suggests that memoryless local search succeeds precisely while the connected manifold remains locally stable.

Load-bearing premise

The local entropy bias is assumed to correctly identify the manifold of connected solutions whose stability governs algorithmic success in the symmetric binary perceptron.

What would settle it

If a Monte Carlo simulation designed to target connected solutions stops finding them at a threshold noticeably different from the predicted κ^{no-mem}_{loc. stab.}, the claimed stability of the delocalized cluster would be falsified.

Figures

Figures reproduced from arXiv: 2505.20954 by Damien Barbier.

Figure 1
Figure 1. Figure 1: Drawing representing the local arrangement of solutions [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Drawing representing the connected structure introduced to evaluate [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Drawing representing a star-shaped cluster of the connected minima. To obtain this [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Representation of the perturbation in the no-memory cluster(s). While along a no [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Plot indicating the sign of the perturbation [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Phase diagram compiling all the different transitions we showed in the SBP solutions [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Plot representing the different transitions occurring when tuning [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: To determine the nature of the clustering below κ no−mem. loc. stab. , we plot in [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 8
Figure 8. Figure 8: Plot showing the decorrelation time tdec. as a function of κ. Each annealing setup (α = {0.3, 0.5, 0.75} and N = {1250, 2500, 500, 104}) is simulated five times. Each point in the plot indicates a decorrelation time obtained for a given simulation and a given round of annealing. In the shades of red (respectively blue and green), we have the simulations for α = 0.3 (respectively α = 0.5 and α = 0.75). The … view at source ↗
Figure 9
Figure 9. Figure 9: Plot showing the ratio between the total number of rejected spin flips [PITH_FULL_IMAGE:figures/full_fig_p022_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Plots of the correlation functions xt · x0/N (obtained for each round of annealing) as a function of the rescaled time γ(κ)t. Each color corresponds to different value for α, red is α = 0.3, blue is α = 0.5 and green is α = 0.75. The solid lines are averages over five entire annealing procedures, for each setup (α = {0.3, 0.5, 0.75} and N = {1250, 2500, 500, 104}). For a given value of α -i.e. a given col… view at source ↗
Figure 11
Figure 11. Figure 11: Plots displaying the distribution of margins at the end of annealing procedures, for [PITH_FULL_IMAGE:figures/full_fig_p024_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Plots displaying the Franz-Parisi potential defined in Eq. (135) as a function of the [PITH_FULL_IMAGE:figures/full_fig_p037_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Schematic representation for the landscape of equilibrated systems ( [PITH_FULL_IMAGE:figures/full_fig_p038_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Plots displaying the behavior of the Franz-Parisi potential defined in Eq. (151) as a [PITH_FULL_IMAGE:figures/full_fig_p041_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Plot showing the decorrelation time tdec. as a function of κ for a single annealing procedure. We tested the annealing setups (α = {0.3, 0.5, 0.75} and N = {750, 1250, 2500, 5000}) with the new cost Gˆenerg λtop [·] -see Eq. (164)-. Each point in the plot indicates a decorrelation time obtained for a given round of annealing. In the shades of red (respectively blue and green), we have the simulations for … view at source ↗
read the original abstract

We define and study a statistical mechanics ensemble that characterizes connected solutions in constraint satisfaction problems (CSPs). Built around a well-known local entropy bias, it allows us to better identify hardness transitions in problems where the energy landscape is dominated by isolated solutions. We apply this new device to the symmetric binary perceptron model (SBP), and study how its manifold of connected solutions behaves. We choose this particular problem because, while its typical solutions are isolated, it can be solved using local algorithms for a certain range of constraint density $\alpha$ and threshold $\kappa$. With this new ensemble, we unveil the presence of a cluster composed of delocalized connected solutions. In particular, we demonstrate its stability until a critical threshold $\kappa^{\rm no-mem}_{\rm loc.\, stab.}$ (dependent on $\alpha$). This transition appears as paths of solutions shatter, a phenomenon that more conventional statistical mechanics approaches fail to grasp. Finally, we compared our predictions to simulations. For this, we used a modified Monte-Carlo algorithm, designed specifically to target these delocalized solutions. We obtained, as predicted, that the algorithm finds solutions until $\kappa\approx\kappa^{\rm no-mem}_{\rm loc.\, stab.}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a statistical mechanics ensemble based on a local entropy bias to characterize the manifold of connected (delocalized) solutions in constraint satisfaction problems. Applied to the symmetric binary perceptron (SBP), where typical solutions are isolated, the ensemble reveals a cluster of connected solutions whose local stability persists up to a critical threshold κ^{no-mem}_{loc. stab.}(α). This transition, at which paths of solutions shatter, is not captured by standard approaches; the prediction is compared to the success of a custom Monte-Carlo sampler designed to target high-local-entropy regions.

Significance. If the local-entropy bias correctly identifies the relevant connected manifold, the work supplies a new device for locating algorithmic thresholds in glassy CSP landscapes dominated by isolated solutions. The explicit matching between the derived stability threshold and the performance limit of the modified sampler is a concrete strength that supports the claim and could generalize to other problems where conventional replica analyses miss connectivity.

major comments (2)
  1. [§4] §4 (ensemble definition and stability calculation): the local entropy bias is introduced to weight connected solutions, yet the derivation of κ^{no-mem}_{loc. stab.} does not demonstrate that this bias is measure-theoretically independent of the algorithmic dynamics; if the bias over-selects atypical high-entropy regions, the reported stability threshold may not bound unmodified local search or message-passing success in the SBP.
  2. [§5.2] §5.2 (Monte-Carlo validation): the custom sampler is constructed to target the same delocalized solutions that define the ensemble; without an ablation against an unmodified local Monte-Carlo or message-passing dynamics, and without reported finite-size scaling or error analysis on the observed success threshold, the numerical agreement cannot be taken as independent confirmation that the theoretical transition controls algorithmic reachability.
minor comments (2)
  1. [Abstract] The abstract introduces the symbol κ^{no-mem}_{loc. stab.} without a brief parenthetical gloss, which may hinder readers who have not yet reached the main text.
  2. [Figures] Figure captions (e.g., Fig. 2) omit the number of disorder realizations and the precise definition of the plotted order parameter; adding these details would improve reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our manuscript. We appreciate the recognition of the potential significance of our approach for identifying algorithmic thresholds in glassy landscapes. Below, we provide detailed responses to the major comments, outlining how we plan to address them in the revised version.

read point-by-point responses

  1. Referee: [§4] §4 (ensemble definition and stability calculation): the local entropy bias is introduced to weight connected solutions, yet the derivation of κ^{no-mem}_{loc. stab.} does not demonstrate that this bias is measure-theoretically independent of the algorithmic dynamics; if the bias over-selects atypical high-entropy regions, the reported stability threshold may not bound unmodified local search or message-passing success in the SBP.

    Authors: We thank the referee for highlighting this important aspect. The local entropy bias is a static reweighting of the solution space based on the local density of solutions, which is a geometric property independent of any particular search dynamics. The ensemble is constructed to select for configurations with high local entropy, thereby focusing on the delocalized connected component. The stability analysis is performed by examining the fluctuations within this biased measure, revealing the point at which the connected cluster becomes unstable. We acknowledge that this threshold characterizes the stability under the biased ensemble and may not directly apply to unmodified dynamics that do not preferentially select high-entropy regions. However, it provides a theoretical characterization of the connected manifold that conventional approaches miss. In the revised manuscript, we will expand the discussion in §4 to clarify the measure-theoretic definition and explicitly state the scope regarding algorithmic implications for biased versus unbiased search. revision: partial

  2. Referee: [§5.2] §5.2 (Monte-Carlo validation): the custom sampler is constructed to target the same delocalized solutions that define the ensemble; without an ablation against an unmodified local Monte-Carlo or message-passing dynamics, and without reported finite-size scaling or error analysis on the observed success threshold, the numerical agreement cannot be taken as independent confirmation that the theoretical transition controls algorithmic reachability.

    Authors: We agree with the referee that the Monte-Carlo sampler is tailored to the high-local-entropy regions identified by our ensemble, making the numerical results a consistency check rather than fully independent validation. To address this, we will include an ablation study comparing the performance of the custom sampler to a standard local Monte-Carlo algorithm without the entropy bias. Additionally, we will report finite-size scaling of the success probability across different system sizes and include error analysis on the estimated success thresholds. These additions will strengthen the evidence that the theoretical transition marks the limit of algorithmic reachability for methods that target the connected manifold. revision: yes

Circularity Check

1 steps flagged

Tailored Monte-Carlo sampler targeting the local-entropy ensemble renders stability threshold validation self-confirming

specific steps
  1. fitted input called prediction [Abstract (simulation comparison paragraph)]
    "we used a modified Monte-Carlo algorithm, designed specifically to target these delocalized solutions. We obtained, as predicted, that the algorithm finds solutions until κ≈κ^{no-mem}_{loc. stab.}."

    The ensemble is built around the local entropy bias precisely to select the delocalized connected solutions. The Monte-Carlo is then altered to target the identical manifold, and its success up to the derived threshold is offered as confirmation. The agreement is therefore enforced by the shared targeting criterion rather than constituting an independent test of whether the threshold governs standard local algorithms.

full rationale

The derivation defines an ensemble via local entropy bias to isolate the manifold of connected/delocalized solutions in the SBP, derives a stability threshold κ^{no-mem}_{loc. stab.}, and then validates it by running a Monte-Carlo algorithm that is explicitly modified to target precisely those same solutions. Because the sampler is constructed to align with the ensemble definition rather than being an unmodified local search or message-passing dynamics, the reported agreement up to the threshold reduces to a consistency check within the biased measure. This constitutes a fitted-input-called-prediction pattern for the central algorithmic claim. No self-citation chains or definitional loops appear in the abstract or described construction; the circularity is localized to the simulation comparison that bears the load for claiming relevance to algorithmic success.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The ensemble rests on the local entropy bias as the defining bias for connected solutions; the SBP model parameters α and κ are treated as external inputs. No new particles or forces are introduced.

free parameters (2)
  • constraint density α
    Model parameter varied to study dependence of the threshold
  • threshold κ
    Varied to locate the stability transition of the connected cluster
axioms (1)
  • domain assumption Local entropy bias characterizes the manifold of connected solutions
    Used to define the statistical mechanics ensemble

pith-pipeline@v0.9.0 · 5747 in / 1216 out tokens · 33929 ms · 2026-05-19T13:35:17.335214+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages · 2 internal anchors

  1. [1]

    World Scientific Publishing Company, 1987

    Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro.Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987

    work page 1987

  2. [2]

    L. F. Cugliandolo and J. Kurchan. Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model.Phys. Rev. Lett., 71:173–176, Jul 1993

    work page 1993

  3. [3]

    Dynamical instantons and activated processes in mean-field glass models.SciPost Physics, 10:002, 1 2021

    Valentina Ros, Giulio Biroli, and Chiara Cammarota. Dynamical instantons and activated processes in mean-field glass models.SciPost Physics, 10:002, 1 2021

    work page 2021

  4. [4]

    Gibbs states and the set of solutions of random constraint satisfaction problems.Proceedings of the National Academy of Sciences, 104(25):10318–10323, 2007

    Florent Krzakała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems.Proceedings of the National Academy of Sciences, 104(25):10318–10323, 2007

    work page 2007

  5. [5]

    Fear and Trevor Price

    Karen K. Fear and Trevor Price. The adaptive surface in ecology.Oikos, 82:440, 9 1998

    work page 1998

  6. [6]

    Hatton, Onofrio Mazzarisi, Ada Altieri, and Matteo Smerlak

    Ian A. Hatton, Onofrio Mazzarisi, Ada Altieri, and Matteo Smerlak. Diversity begets stability: Sublinear growth and competitive coexistence across ecosystems.Science, 383, 3 2024

    work page 2024

  7. [7]

    Bärbel M. R. Stadler and Peter F. Stadler. Generalized topological spaces in evolutionary theory and combinatorial chemistry.Journal of Chemical Information and Computer Sciences, 42:577–585, 5 2002

    work page 2002

  8. [8]

    Transition paths in potts-like energy landscapes: General properties and application to protein sequence models.Physical Review E, 108:024141, 8 2023

    Eugenio Mauri, Simona Cocco, and Rémi Monasson. Transition paths in potts-like energy landscapes: General properties and application to protein sequence models.Physical Review E, 108:024141, 8 2023

    work page 2023

  9. [9]

    Adaptation in protein fitness landscapes is facilitated by indirect paths.eLife, 5:e16965, 7 2016

    Nicholas C Wu, Lei Dai, C Anders Olson, James O Lloyd-Smith, and Ren Sun. Adaptation in protein fitness landscapes is facilitated by indirect paths.eLife, 5:e16965, 7 2016

    work page 2016

  10. [10]

    Disordered systems insights on computational hardness.Journal of Statistical Mechanics: Theory and Experiment, 2022:114015, 11 2022

    David Gamarnik, Cristopher Moore, and Lenka Zdeborová. Disordered systems insights on computational hardness.Journal of Statistical Mechanics: Theory and Experiment, 2022:114015, 11 2022

    work page 2022

  11. [11]

    Analytic and algorithmic solution of random satisfiability problems.Science, 297(5582):812–815, 2002

    Marc Mézard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems.Science, 297(5582):812–815, 2002

    work page 2002

  12. [12]

    Donoho, Arian Maleki, and Andrea Montanari

    David L. Donoho, Arian Maleki, and Andrea Montanari. Message Passing Algorithms for Compressed Sensing.Proceedings of the National Academy of Sciences, 106:18914–18919, 2009

    work page 2009

  13. [13]

    The algorithmic hardness threshold for continuous random energy models

    Louigi Addario-Berry and Pascal Maillard. The algorithmic hardness threshold for continuous random energy models.arXiv:1810.05129, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  14. [14]

    A rugged yet easily navigable fitness landscape of antibiotic resistance.bioRxiv, 2023

    Andrei Papkou, Lucia Garcia-Pastor, José Antonio Escudero, and Andreas Wagner. A rugged yet easily navigable fitness landscape of antibiotic resistance.bioRxiv, 2023

    work page 2023

  15. [15]

    The structure of genotype-phenotype maps makes fitness landscapes navigable.Nature Ecology and Evolution, 6:1742–1752, 2022

    S F Greenbury, A A Louis, and S E Ahnert. The structure of genotype-phenotype maps makes fitness landscapes navigable.Nature Ecology and Evolution, 6:1742–1752, 2022

    work page 2022

  16. [16]

    Macadangdang, Sara K

    Benjamin R. Macadangdang, Sara K. Makanani, and Jeff F. Miller. Accelerated evolution by diversity-generating retroelements.Annual Review of Microbiology, 76:389–411, 9 2022. 44

    work page 2022

  17. [17]

    Infinite number of order parameters for spin-glasses.Physical Review Letters, 43(23):1754, 1979

    Giorgio Parisi. Infinite number of order parameters for spin-glasses.Physical Review Letters, 43(23):1754, 1979

    work page 1979

  18. [18]

    Thouless, Philip W

    David J. Thouless, Philip W. Anderson, and Richard G. Palmer. Solution of’solvable model of a spin glass’.Philosophical Magazine, 35(3):593–601, 1977

    work page 1977

  19. [19]

    S. Wright. The roles of mutation, inbreeding, crossbreeding and selection in evolution. Proceedings of the XI International Congress of Genetics, 8:209–222, 1932

    work page 1932

  20. [20]

    Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 79:2554–2558, 4 1982

    J J Hopfield. Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 79:2554–2558, 4 1982

    work page 1982

  21. [21]

    Optimal storage properties of neural network models

    Elizabeth Gardner and Bernard Derrida. Optimal storage properties of neural network models. Journal of Physics A: Mathematical and general, 21(1):271, 1988

    work page 1988

  22. [22]

    The overlap gap property: A topological barrier to optimizing over random structures.Proceedings of the National Academy of Sciences, 118(41), 2021

    David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures.Proceedings of the National Academy of Sciences, 118(41), 2021

    work page 2021

  23. [23]

    On the solution-space geometry of random constraint satisfaction problems.Random Structures & Algorithms, 38:251–268, 5 2011

    Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems.Random Structures & Algorithms, 38:251–268, 5 2011

    work page 2011

  24. [24]

    Limits of local algorithms over sparse random graphs

    David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. InProceedings of the 5th conference on Innovations in theoretical computer science, pages 369–376. ACM, 2014

    work page 2014

  25. [25]

    Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference.Journal of Molecular Evolution, 43:304–311, 9 1996

    Bruce Rannala and Ziheng Yang. Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference.Journal of Molecular Evolution, 43:304–311, 9 1996

    work page 1996

  26. [26]

    Huelsenbeck, Fredrik Ronquist, Rasmus Nielsen, and Jonathan P

    John P. Huelsenbeck, Fredrik Ronquist, Rasmus Nielsen, and Jonathan P. Bollback. Bayesian inference of phylogeny and its impact on evolutionary biology.Science, 294:2310–2314, 12 2001

    work page 2001

  27. [27]

    Malatesta, Gabriele Perugini, Fabrizio Pittorino, and Luca Saglietti

    Brandon Livio Annesi, Clarissa Lauditi, Carlo Lucibello, Enrico M. Malatesta, Gabriele Perugini, Fabrizio Pittorino, and Luca Saglietti. Star-shaped space of solutions of the spherical negative perceptron.Physical Review Letters, 131:227301, 11 2023

    work page 2023

  28. [28]

    Storage capacity of memory networks with binary couplings

    Werner Krauth and Marc Mézard. Storage capacity of memory networks with binary couplings. Journal de Physique, 50(20):3057–3066, 1989

    work page 1989

  29. [29]

    Clustering of solutions in the symmetric binary perceptron.Journal of Statistical Mechanics: Theory and Experiment, 2020(7):073303, 2020

    Carlo Baldassi, Riccardo Della Vecchia, Carlo Lucibello, and Riccardo Zecchina. Clustering of solutions in the symmetric binary perceptron.Journal of Statistical Mechanics: Theory and Experiment, 2020(7):073303, 2020

    work page 2020

  30. [30]

    Storage capacity in symmetric binary perceptrons.Journal of Physics A: Mathematical and Theoretical, 52(29):294003, 2019

    Benjamin Aubin, Will Perkins, and Lenka Zdeborova. Storage capacity in symmetric binary perceptrons.Journal of Physics A: Mathematical and Theoretical, 52(29):294003, 2019

    work page 2019

  31. [31]

    Learning by message passing in networks of discrete synapses.Physical review letters, 96(3):030201, 2006

    Alfredo Braunstein and Riccardo Zecchina. Learning by message passing in networks of discrete synapses.Physical review letters, 96(3):030201, 2006

    work page 2006

  32. [32]

    On-line balancing of random inputs.Random Structures & Algorithms, 57(4):879–891, 2020

    Nikhil Bansal and Joel H Spencer. On-line balancing of random inputs.Random Structures & Algorithms, 57(4):879–891, 2020

    work page 2020

  33. [33]

    On the atypical solutions of the symmetric binary perceptron.Journal of Physics A: Mathematical and Theoretical, 57(19):195202, 2024

    Damien Barbier, Ahmed El Alaoui, Florent Krzakala, and Lenka Zdeborová. On the atypical solutions of the symmetric binary perceptron.Journal of Physics A: Mathematical and Theoretical, 57(19):195202, 2024. 45

    work page 2024

  34. [34]

    Capacity threshold for the ising perceptron

    Brice Huang. Capacity threshold for the ising perceptron. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1126–1136. IEEE, 10 2024

    work page 2024

  35. [35]

    Recipes for metastable states in spin glasses.Journal de Physique I, 5(11):1401–1415, 1995

    Silvio Franz and Giorgio Parisi. Recipes for metastable states in spin glasses.Journal de Physique I, 5(11):1401–1415, 1995

    work page 1995

  36. [36]

    Quasi-equilibrium in glassy dynamics: an algebraic view

    Silvio Franz and Giorgio Parisi. Quasi-equilibrium in glassy dynamics: an algebraic view. Journal of Statistical Mechanics: Theory and Experiment, 2013(02):P02003, feb 2013

    work page 2013

  37. [37]

    Quasi equilibrium construction for the long time limit of glassy dynamics.Journal of Statistical Mechanics: Theory and Experiment, 2015(10):P10010, oct 2015

    Silvio Franz, Giorgio Parisi, Federico Ricci-Tersenghi, and Pierfrancesco Urbani. Quasi equilibrium construction for the long time limit of glassy dynamics.Journal of Statistical Mechanics: Theory and Experiment, 2015(10):P10010, oct 2015

    work page 2015

  38. [38]

    How to escape atypical regions in the symmetric binary perceptron: A journey through connected-solutions states.SciPost Physics, 18:115, 3 2025

    Damien Barbier. How to escape atypical regions in the symmetric binary perceptron: A journey through connected-solutions states.SciPost Physics, 18:115, 3 2025

    work page 2025

  39. [39]

    Statistical physics-based reconstruction in compressed sensing

    F. Krzakala, M. Mézard, F. Sausset, Y. Sun, and L. Zdeborova. Statistical physics-based reconstruction in compressed sensing.arXiv:1109.4424, 2011

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  40. [40]

    Alain Barrat, Silvio Franz, and Giorgio Parisi. Temperature evolution and bifurcations of metastable states in mean-field spin glasses, with connections with structural glasses.Journal of Physics A: Mathematical and General, 30:5593–5612, 8 1997

    work page 1997

  41. [41]

    Barbier, C

    D. Barbier, C. Lucibello, L. Saglietti, F. Krzakala, and L. Zdeborová. Compressed sensing with l0-norm: statistical physics analysis & algorithms for signal recovery. In2023 IEEE Information Theory Workshop (ITW), pages 323–328. IEEE, 4 2023

    work page 2023

  42. [42]

    Marvels and pitfalls of the langevin algorithm in noisy high-dimensional inference.Physical Review X, 10:011057, 3 2020

    Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Marvels and pitfalls of the langevin algorithm in noisy high-dimensional inference.Physical Review X, 10:011057, 3 2020

    work page 2020

  43. [43]

    Local entropy as a measure for sampling solutions in constraint satisfaction problems.Journal of Statistical Mechanics: Theory and Experiment, 2016(2):023301, 2016

    Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Local entropy as a measure for sampling solutions in constraint satisfaction problems.Journal of Statistical Mechanics: Theory and Experiment, 2016(2):023301, 2016

    work page 2016

  44. [44]

    Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses.Physical review letters, 115(12):128101, 2015

    Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses.Physical review letters, 115(12):128101, 2015

    work page 2015

  45. [45]

    Unveiling the structure of wide flat minima in neural networks.Physical Review Letters, 127(27):278301, 2021

    Carlo Baldassi, Clarissa Lauditi, Enrico M Malatesta, Gabriele Perugini, and Riccardo Zecchina. Unveiling the structure of wide flat minima in neural networks.Physical Review Letters, 127(27):278301, 2021

    work page 2021

  46. [46]

    Wide flat minima and optimal generalization in classifying high-dimensional gaussian mixtures.Journal of Statistical Mechanics: Theory and Experiment, 2020:124012, 12 2020

    Carlo Baldassi, Enrico M Malatesta, Matteo Negri, and Riccardo Zecchina. Wide flat minima and optimal generalization in classifying high-dimensional gaussian mixtures.Journal of Statistical Mechanics: Theory and Experiment, 2020:124012, 12 2020

    work page 2020

  47. [47]

    Clustering of solutions in the symmetric binary perceptron.Journal of Statistical Mechanics: Theory and Experiment, 2020:073303, 7 2020

    Carlo Baldassi, Riccardo Della Vecchia, Carlo Lucibello, and Riccardo Zecchina. Clustering of solutions in the symmetric binary perceptron.Journal of Statistical Mechanics: Theory and Experiment, 2020:073303, 7 2020

    work page 2020

  48. [48]

    Shaping the learning landscape in neural networks around wide flat minima.Proceedings of the National Academy of Sciences, 117:161–170, 1 2020

    Carlo Baldassi, Fabrizio Pittorino, and Riccardo Zecchina. Shaping the learning landscape in neural networks around wide flat minima.Proceedings of the National Academy of Sciences, 117:161–170, 1 2020. 46

    work page 2020

  49. [49]

    Carlo Baldassi, Christian Borgs, Jennifer T Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes.Proceedings of the National Academy of Sciences, 113(48):E7655–E7662, 2016

    work page 2016

  50. [50]

    Efficiency of quantum vs

    Carlo Baldassi and Riccardo Zecchina. Efficiency of quantum vs. classical annealing in nonconvex learning problems.Proceedings of the National Academy of Sciences, 115:1457– 1462, 2 2018

    work page 2018

  51. [51]

    Frozen glass phase in the multi-index matching problem.Physical review letters, 93(21):217205, 2004

    OC Martin and M Mézard. Frozen glass phase in the multi-index matching problem.Physical review letters, 93(21):217205, 2004

    work page 2004

  52. [52]

    Locked constraint satisfaction problems.Physical review letters, 101(7):078702, 2008

    Lenka Zdeborová and Marc Mézard. Locked constraint satisfaction problems.Physical review letters, 101(7):078702, 2008

    work page 2008

  53. [53]

    Entropy landscape of solutions in the binary perceptron problem.Journal of Physics A: Mathematical and Theoretical, 46(37):375002, 2013

    Haiping Huang, KY Michael Wong, and Yoshiyuki Kabashima. Entropy landscape of solutions in the binary perceptron problem.Journal of Physics A: Mathematical and Theoretical, 46(37):375002, 2013

    work page 2013

  54. [54]

    Origin of the computational hardness for learning with binary synapses.Physical Review E, 90(5):052813, 2014

    Haiping Huang and Yoshiyuki Kabashima. Origin of the computational hardness for learning with binary synapses.Physical Review E, 90(5):052813, 2014

    work page 2014

  55. [55]

    The asymptotics of the clustering transition for random constraint satisfaction problems.Journal of Statistical Physics, 181, 12 2020

    Louise Budzynski and Guilhem Semerjian. The asymptotics of the clustering transition for random constraint satisfaction problems.Journal of Statistical Physics, 181, 12 2020

    work page 2020

  56. [56]

    J. M. Kosterlitz, D. J. Thouless, and Raymund C. Jones. Spherical model of a spin-glass. Physical Review Letters, 36:1217–1220, 5 1976

    work page 1976

  57. [57]

    Diversity-generating retroelements.Current Opinion in Microbiology, 10:388–395, 8 2007

    Bob Medhekar and Jeff F Miller. Diversity-generating retroelements.Current Opinion in Microbiology, 10:388–395, 8 2007

    work page 2007

  58. [58]

    Harnessing diversity generating retroelements for in vivo targeted hyper-mutagenesis

    Raphael Laurenceau, Paul Rochette, Elena Lopez-Rodriguez, Catherine Fan, Amandine Maire, Paul Vittot, Karol Melissa Cerdas-Mejias, Auguste Bouvier, Thea Chrysostomou, and David Bikard. Harnessing diversity generating retroelements for in vivo targeted hyper-mutagenesis. bioRxiv, 2025

    work page 2025

  59. [59]

    Marc Potters and Jean-Philippe Bouchaud.A First Course in Random Matrix Theory: for Physicists, Engineers and Data Scientists. 11 2020

    work page 2020

  60. [60]

    Algorithms and barriers in the symmetric binary perceptron model.arXiv preprint arXiv:2203.15667, 2022

    David Gamarnik, Eren C Kızıldağ, Will Perkins, and Changji Xu. Algorithms and barriers in the symmetric binary perceptron model.arXiv preprint arXiv:2203.15667, 2022. 47

    work page arXiv 2022