Harnessing the Bethe free energy

DOI10.1002/rsa.20692zbMath1352.05162arXiv1504.03975OpenAlexW904137795WikidataQ41886426 ScholiaQ41886426MaRDI QIDQ2953696

Amin Coja-Oghlan, Victor Bapst

Publication date: 5 January 2017

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.03975

zbMATH Keywords

random graphsregularity lemmacavity methodbelief propagation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Related Items (16)

Phase transitions in discrete structures ⋮ Information-theoretic thresholds from the cavity method ⋮ Strong replica symmetry in high-dimensional optimal Bayesian inference ⋮ Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation ⋮ Metastability of the Potts ferromagnet on random regular graphs ⋮ Replica symmetry breaking without replicas ⋮ Bethe states of random factor graphs ⋮ Charting the replica symmetric phase ⋮ Charting the replica symmetric phase ⋮ The satisfiability threshold for random linear equations ⋮ Spin systems on Bethe lattices ⋮ The number of solutions for random regular NAE-SAT ⋮ The Cut Metric for Probability Distributions ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Belief propagation on the random \(k\)-SAT model ⋮ The rank of sparse random matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A positive temperature phase transition in random hypergraph 2-coloring
• Spin glass models from the point of view of spin distributions
• Antiferromagnetic Potts model on the Erdős-Rényi random graph
• Large deviations of empirical neighborhood distribution in sparse random graphs
• The asymptotic \(k\)-SAT threshold
• Ising models on locally tree-like graphs
• On the hardness of sampling independent sets beyond the tree threshold
• Representations for partially exchangeable arrays of random variables
• Bounds for diluted mean-fields spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• Limits of discrete distributions and Gibbs measures on random graphs
• Factor models on locally tree-like graphs
• The replica symmetric solution for Potts models on \(d\)-regular graphs
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Proof of the Satisfiability Conjecture for Large k
• Graph Theory and Probability
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Modern Coding Theory
• On the maximum satisfiability of random formulas
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Information, Physics, and Computation
• Almost all regular graphs are hamiltonian
• The condensation phase transition in the regular $k$-SAT model
• Belief Propagation on replica symmetric random factor graph models
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The Sherrington-Kirkpatrick Model
• Satisfiability threshold for random regular NAE-SAT
• Harnessing the Bethe Free Energy
• Gibbs states and the set of solutions of random constraint satisfaction problems
• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• Some remarks on the theory of graphs
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Probability
• The two possible values of the chromatic number of a random graph
• The condensation phase transition in random graph coloring

This page was built for publication: Harnessing the Bethe free energy