Information-theoretic thresholds from the cavity method
Publication:1649349
DOI10.1016/j.aim.2018.05.029zbMath1397.82013arXiv1611.00814WikidataQ59459996 ScholiaQ59459996MaRDI QIDQ1649349
Will Perkins, Amin Coja-Oghlan, Lenka Zdeborová, Florent Krzakala
Publication date: 5 July 2018
Published in: Advances in Mathematics, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.00814
phase transitions; random graphs; Gibbs measures; stochastic block model; cavity method; belief propagation; information theoretic thresholds; random graph coloring
05C80: Random graphs (graph-theoretic aspects)
82B26: Phase transitions (general) in equilibrium statistical mechanics
82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
05C15: Coloring of graphs and hypergraphs
82D40: Statistical mechanics of magnetic materials
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- On the Potts antiferromagnet on random graphs
- Community detection in sparse networks via Grothendieck's inequality
- The asymptotic \(k\)-SAT threshold
- Gibbs measures and phase transitions on sparse random graphs
- The concentration of the chromatic number of random graphs
- A general limit theorem for recursive algorithms and combinatorial structures
- A proof of the block model threshold conjecture
- 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
- The cavity method at zero temperature
- On the chromatic number of a random hypergraph
- 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
- The Parisi formula
- Public-key cryptography from different assumptions
- Proof of the Satisfiability Conjecture for Large k
- On the Complexity of Random Satisfiability Problems with Planted Solutions
- Harnessing the Bethe free energy
- Spatial Coupling as a Proof Technique and Three Applications
- Reconstruction and Clustering in Random Constraint Satisfaction Problems
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Tight Bounds for LDPC and LDGM Codes Under MAP Decoding
- Griffith–Kelly–Sherman Correlation Inequalities: A Useful Tool in the Theory of Error Correcting Codes
- Graph Partitioning via Adaptive Spectral Techniques
- Relations between average case complexity and approximation complexity
- Maxwell Construction: The Hidden Bridge Between Iterative and Maximuma PosterioriDecoding
- Information, Physics, and Computation
- A Spectral Technique for Coloring Random 3-Colorable Graphs
- On the 2-colorability of random hypergraphs
- Optimization problems and replica symmetry breaking in finite connectivity spin glasses
- Bounds for Random Constraint Satisfaction Problems via Spatial Coupling
- Asymptotic mutual information for the balanced binary stochastic block model
- Belief Propagation on replica symmetric random factor graph models
- The Sherrington-Kirkpatrick Model
- The Generalized Area Theorem and Some of its Consequences
- Community detection thresholds and the weak Ramanujan property
- The phase transition in inhomogeneous random graphs
- Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation
- Semidefinite programs on sparse random graphs and their application to community detection
- Planting Colourings Silently
- Gibbs states and the set of solutions of random constraint satisfaction problems
- The freezing threshold for k-colourings of a random graph
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Optimal Transport
- The chromatic number of random graphs
- The chromatic number of random graphs
- Almost all graphs with average degree 4 are 3-colorable
- Satisfiability threshold for random regular \textsc{nae-sat}
- The condensation phase transition in random graph coloring