Bethe states of random factor graphs

DOI10.1007/s00220-019-03387-7zbMath1412.82016arXiv1709.03827OpenAlexW2963867298WikidataQ128385081 ScholiaQ128385081MaRDI QIDQ1733816

Amin Coja-Oghlan, Will Perkins

Publication date: 21 March 2019

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

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

zbMATH Keywords

Gibbs measurereplica symmetry breakingBethe statesrandom factor graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Symmetry breaking in quantum theory (81R40) Exactly solvable models; Bethe ansatz (82B23)

Related Items (7)

Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation ⋮ Shattering versus metastability in spin glasses ⋮ Multi-variate correlation and mixtures of product measures ⋮ Spin systems on Bethe lattices ⋮ The Cut Metric for Probability Distributions ⋮ Belief propagation on the random \(k\)-SAT model ⋮ Belief propagation: accurate marginals or accurate partition function—where is the difference?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Antiferromagnetic Potts model on the Erdős-Rényi random graph
• Counting in two-spin models on \(d\)-regular graphs
• Reconstruction and estimation in the planted partition model
• On the Potts antiferromagnet on random graphs
• On the replica symmetric solution of the \(K\)-sat model
• Limits of dense graph sequences
• The asymptotic \(k\)-SAT threshold
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Gibbs measures and phase transitions on sparse random graphs
• On the hardness of sampling independent sets beyond the tree threshold
• Quick approximation to matrices and applications
• Replica symmetry breaking in short-range spin glasses: Theoretical foundations and numerical evidences
• Belief propagation on replica symmetric random factor graph models
• Information-theoretic thresholds from the cavity method
• A proof of the block model threshold conjecture
• The cavity method at zero temperature
• Thouless-Anderson-Palmer equations for generic \(p\)-spin glasses
• Limits of discrete distributions and Gibbs measures on random graphs
• Maximum independent sets on random regular graphs
• Factor models on locally tree-like graphs
• The replica symmetric solution for Potts models on \(d\)-regular graphs
• Proof of the Satisfiability Conjecture for Large k
• Harnessing the Bethe free energy
• Spatial Coupling as a Proof Technique and Three Applications
• Modern Coding Theory
• Graph limits and exchangeable random graphs
• Information, Physics, and Computation
• Proof of the Achievability Conjectures for the General Stochastic Block Model
• The Sherrington-Kirkpatrick Model
• Community detection thresholds and the weak Ramanujan property
• Graphons, cut norm and distance, couplings and rearrangements
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The high temperature case for the random \(K\)-sat problem

This page was built for publication: Bethe states of random factor graphs