Rigorous decimation-based construction of ground pure states for spin glass models on random lattices

Abstract

A constructive scheme for determining pure states (clusters) at very low temperature in the 3-spins glass model on a random lattice is provided, in full agreement with Parisi's one step replica symmetry breaking (RSB) scheme. Proof is based on the analysis of an exact decimation procedure. When the number c of couplings per spin is smaller than some critical value c_d, all spins are eliminated at the end of decimation (RS phase). In the range c_d<c<c_s, a reduced Hamiltonian is left; each ground state (GS) of the latter is a "seed" from which a cluster of GS of the original Hamiltonian can be reconstructed. Above c_s, GS are frustrated with an energy per spin larger than -c. The number of GS in each cluster, the number of clusters, the distances between GS are calculated and correspond to RSB predictions.

Cited by in corpus (68)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• Survey propagation: an algorithm for satisfiability
• The number of matchings in random graphs
• Survey Propagation as local equilibrium equations
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• On the freezing of variables in random constraint satisfaction problems
• On the dynamics of the glass transition on Bethe lattices
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Finite size scaling for the core of large random hypergraphs
• Survey-propagation decimation through distributed local computations
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Lossy data compression with random gates
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Pairs of SAT Assignment in Random Boolean Formulae
• From Large Scale Rearrangements to Mode Coupling Phenomenology
• Geometrical organization of solutions to random linear Boolean equations
• Controllability and maximum matchings of complex networks
• Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
• Random subcubes as a toy model for constraint satisfaction problems
• Disordered Systems Insights on Computational Hardness
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Core percolation and onset of complexity in Boolean networks
• A frozen glass phase in the multi-index matching problem
• Analysis of LDGM and compound codes for lossy compression and binning
• The large deviations of the whitening process in random constraint satisfaction problems
• Aging dynamics of heterogeneous spin models
• Computational core and fixed-point organisation in Boolean networks
• Statistical mechanics of error exponents for error-correcting codes
• Bicoloring Random Hypergraphs
• Role of fluctuations in the phase transitions of coupled plaquette spin models of glasses
• The theoretical capacity of the Parity Source Coder
• Approximate analysis of search algorithms with "physical" methods
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory
• Low-density graph codes that are optimal for source/channel coding and binning
• The set of solutions of random XORSAT formulae
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Clustering in Hilbert space of a quantum optimization problem
• Two faces of greedy leaf removal procedure on graphs
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• The stripping process can be slow: part I
• Propagation of external regulation and asynchronous dynamics in random Boolean networks
• Phase Transition for Random Quantified XOR-Formulas
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Susceptibility Propagation for Constraint Satisfaction Problems
• Barriers and local minima in energy landscapes of stochastic local search
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• A simple one dimensional glassy Kac model
• An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
• From spin glasses to hard satisfiable formulas
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• Inside the clustering window for random linear equations
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Perturbed Message Passing for Constraint Satisfaction Problems
• Inside the clustering threshold for random linear equations
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• Lower Bounds on the Rate-Distortion Function of LDGM Codes