Replica bounds for optimization problems and diluted spin systems
From MaRDI portal
Abstract: In this paper we generalize to the case of diluted spin models and random combinatorial optimization problems a technique recently introduced by Guerra (cond-mat/0205123) to prove that the replica method generates variational bounds for disordered systems. We analyze a family of models that includes the Viana-Bray model, the diluted p-spin model or random XOR-SAT problem, and the random K-SAT problem, showing that the replica method provides an improvable scheme to obtain lower bounds of the free-energy at all temperatures and of the ground state energy. In the case of K-SAT the replica method thus gives upper bounds of the satisfiability threshold.
Recommendations
Cited in
(71)- Phase transitions in discrete structures
- Disorder chaos in some diluted spin Glass models
- Free energy in the mixed p-spin models with vector spins
- Replica bounds by combinatorial interpolation for diluted spin systems
- The full replica symmetry breaking in the Ising spin glass on random regular graph
- Bounds for diluted mean-fields spin glass models
- Convergence of maximum bisection ratio of sparse random graphs
- Two solutions to diluted p-spin models and XORSAT problems
- Threshold saturation in spatially coupled constraint satisfaction problems
- Spin systems on Bethe lattices
- The number of solutions for random regular NAE-SAT
- Typicality and entropy of processes on infinite trees
- Free energy of a diluted spin Glass model with quadratic Hamiltonian
- Strong replica symmetry in high-dimensional optimal Bayesian inference
- Proof of the satisfiability conjecture for large \(k\)
- Concentration of multi-overlaps for random dilute ferromagnetic spin models
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- Structure of 1-RSB asymptotic Gibbs measures in the diluted \(p\)-spin models
- The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference
- Hierarchical exchangeability of pure states in mean field spin glass models
- Minimal contagious sets in random regular graphs
- The marginally stable Bethe lattice spin glass revisited
- Suboptimality of local algorithms for a class of max-cut problems
- Some observations for mean-field spin glass models
- Factor models on locally tree-like graphs
- On the freezing of variables in random constraint satisfaction problems
- A note on the Guerra and Talagrand theorems for mean field spin glasses: the simple case of spherical models
- Ultrametric broken replica symmetry raMOSt
- Fluctuations of the free energy in the diluted SK-model
- Lower bounds on the chromatic number of random graphs
- Improved replica bounds for the independence ratio of random regular graphs
- Phase transitions in discrete structures
- Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models
- On the number of circuits in random graphs
- On the concentration of the number of solutions of random satisfiability formulas
- Interpolation and comparison methods in the mean field spin glass model
- Harnessing the Bethe free energy
- Calculation of the 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
- Random multi-overlap structures for optimization problems
- On the survey-propagation equations in random constraint satisfiability problems
- Spin glass models from the point of view of spin distributions
- Antiferromagnetic Potts model on the Erdős-Rényi random graph
- Upper-bounding the k-colorability threshold by counting covers
- Notes on the polynomial identities in random overlap structures
- Optimization problems and replica symmetry breaking in finite connectivity spin glasses
- Exactly Solvable Hierarchical Optimization Problem Related to Percolation
- Phase transitions in the \(q\)-coloring of random hypergraphs
- Right-convergence of sparse random graphs
- The replica symmetric phase of random constraint satisfaction problems
- The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models
- The number of matchings in random graphs
- THE KAC LIMIT FOR DILUTED SPIN GLASSES
- The interpolation method for random graphs with prescribed degrees
- A new upper bound for random (2 + p)-SAT by flipping two variables
- Dynamical replica analysis of processes on finitely connected random graphs: I. Vertex covering
- Replica bounds for diluted non-Poissonian spin systems
- The Ising Antiferromagnet and Max Cut on Random Regular Graphs
- The number of satisfying assignments of random 2‐SAT formulas
- The rank of sparse random matrices
- Ultrametric identities in glassy models of natural evolution
- Mean field spin Glass models under weak external field
- Existence of the free energy for heavy-tailed spin glasses
- Some rigorous results for the diluted multi-species SK model
- Replica bound for Ising spin glass models in one dimension
- The fractional chromatic number of random graphs
- Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k 3
- Bounds on the ground state energy of quantum p-spin Hamiltonians
- Some rigorous results on the Lévy spin glass model
- Free energy equivalence between mean-field models and nonsparsely diluted mean-field models
- Structural properties of the disordered spherical and other mean field spin models
- Mean field dilute ferromagnet: High temperature and zero temperature behavior
This page was built for publication: Replica bounds for optimization problems and diluted spin systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1870235)
