Replica bounds for optimization problems and diluted spin systems

DOI10.1023/A:1022885828956MaRDI QIDQ1870235zbMATH OpenOpenAlexFDO

Authors Silvio Franz, Michele Leone

Publication date 11 May 2003

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0208280

Mathematics Subject Classification ID

Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

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

• Bounds for diluted mean-fields spin glass models
• Replica bounds for diluted non-Poissonian spin systems
• Charting the replica symmetric phase
• Random multi-overlap structures for optimization problems
• Optimization problems and replica symmetry breaking in finite connectivity spin glasses

Cited in

(66)

• A new upper bound for random \((2 + p)\)-SAT by flipping two variables
• Exactly Solvable Hierarchical Optimization Problem Related to Percolation
• Calculation of the 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• Ultrametric identities in glassy models of natural evolution
• Existence of the free energy for heavy-tailed spin glasses
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• Mean field spin Glass models under weak external field
• Some rigorous results for the diluted multi-species SK model
• Replica bound for Ising spin glass models in one dimension
• Dynamical replica analysis of processes on finitely connected random graphs: I. Vertex covering
• Spin glass models from the point of view of spin distributions
• Replica bounds for diluted non-Poissonian spin systems
• Mean field dilute ferromagnet: High temperature and zero temperature behavior
• Convergence of maximum bisection ratio of sparse random graphs
• THE KAC LIMIT FOR DILUTED SPIN GLASSES
• Bounds for diluted mean-fields spin glass models
• Right-convergence of sparse random graphs
• Fluctuations of the free energy in the diluted SK-model
• Antiferromagnetic Potts model on the Erdős-Rényi random graph
• Strong replica symmetry in high-dimensional optimal Bayesian inference
• On the survey-propagation equations in random constraint satisfiability problems
• Lower bounds on the chromatic number of random graphs
• Notes on the polynomial identities in random overlap structures
• Typicality and entropy of processes on infinite trees
• Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models
• Improved replica bounds for the independence ratio of random regular graphs
• Factor models on locally tree-like graphs
• Spin systems on Bethe lattices
• Upper-bounding the \(k\)-colorability threshold by counting covers
• The replica symmetric phase of random constraint satisfaction problems
• On the number of circuits in random graphs
• Threshold saturation in spatially coupled constraint satisfaction problems
• Phase transitions in discrete structures
• Concentration of multi-overlaps for random dilute ferromagnetic spin models
• Structural properties of the disordered spherical and other mean field spin models
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• Phase transitions in the \(q\)-coloring of random hypergraphs
• The interpolation method for random graphs with prescribed degrees
• Free energy of a diluted spin Glass model with quadratic Hamiltonian
• Minimal contagious sets in random regular graphs
• The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference
• The full replica symmetry breaking in the Ising spin glass on random regular graph
• A note on the Guerra and Talagrand theorems for mean field spin glasses: the simple case of spherical models
• Random multi-overlap structures for optimization problems
• Some observations for mean-field spin glass models
• Proof of the satisfiability conjecture for large \(k\)
• Phase transitions in discrete structures
• The number of solutions for random regular NAE-SAT
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Harnessing the Bethe free energy
• Hierarchical exchangeability of pure states in mean field spin glass models
• Suboptimality of local algorithms for a class of max-cut problems
• Disorder chaos in some diluted spin Glass models
• On the freezing of variables in random constraint satisfaction problems
• Ultrametric broken replica symmetry raMOSt
• The number of matchings in random graphs
• The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models
• Free energy in the mixed \(p\)-spin models with vector spins
• Structure of 1-RSB asymptotic Gibbs measures in the diluted \(p\)-spin models
• The marginally stable Bethe lattice spin glass revisited
• The rank of sparse random matrices
• The number of satisfying assignments of random 2‐SAT formulas
• Replica bounds by combinatorial interpolation for diluted spin systems
• On the concentration of the number of solutions of random satisfiability formulas
• Interpolation and comparison methods in the mean field spin glass model
• Optimization problems and replica symmetry breaking in finite connectivity spin glasses

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)