Exact solutions for diluted spin glasses and optimization problems

Abstract

We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking Ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same Ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p=3, γ_d=0.818 and γ_s=0.918 resp.), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds (γ_c^{var}=4.396 and γ_c^{var}=2.149 resp.).

4 pages, 1 figure, accepted for publication in PRL

References in corpus (1)

• Simplest random K-satisfiability problem

Cited by in corpus (57)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Typical random 3-SAT formulae and the satisfiability threshold
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The glassy phase of Gallager codes
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• First-order transitions and the performance of quantum algorithms in random optimization problems
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• The Dynamic Phase Transition for Decoding Algorithms
• Numerical Results for Ground States of Mean-Field Spin Glasses at low Connectivities
• Glassy behavior induced by geometrical frustration in a hard-core lattice gas model
• Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
• Statistical mechanics of the vertex-cover problem
• The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme
• Charting the replica symmetric phase
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Jamming Model for the Extremal Optimization Heuristic
• Diluted Mean-Field Spin-Glass Models at Criticality
• Trapping of Continuous-Time Quantum walks on Erdos-Renyi graphs
• One step RSB scheme for the rate distortion function
• Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
• Glassy dynamics in granular compaction: sand on random graphs
• Belief propagation for graph partitioning
• Aging dynamics of heterogeneous spin models
• Complexity transitions in global algorithms for sparse linear systems over finite fields
• Metastable configurations of spin models on random graphs
• First- and second-order phase transitions in Ising models on small world networks, simulations and comparison with an effective field theory
• Communication and correlation among communities
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• 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
• Source coding by efficient selection of ground states clusters
• Graph's Topology and Free Energy of a Spin Model on the Graph
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Spin glass phase transitions in the random feedback vertex set problem
• Thermodynamic Construction of an One-Step Replica-Symmetry-Breaking Solution in Finite Connectivity Spin Glasses
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• New Understanding of the Bethe Approximation and the Replica Method
• Phase Transition for Random Quantified XOR-Formulas
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Dynamics of sparse Boolean networks with multi-node and self-interactions
• Barriers and local minima in energy landscapes of stochastic local search
• Realizing interdependent couplings as thermal or higher-order interactions
• Multiple transitions in an infinite range p-spin random-crystal field Blume Capel model
• Optimization and Physics: On the satisfiability of random Boolean formulae
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Supervised and Unsupervised protocols for hetero-associative neural networks
• Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
• Dynamic message-passing approach for kinetic spin models with reversible dynamics
• Replica analysis of Franz-Parisi potential for sparse systems
• Free energy equivalence between mean-field models and nonsparsely diluted mean-field models
• Typical rank of coin-toss power-law random matrices over GF(2)
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks