Information-theoretic thresholds from the cavity method

DOI10.1016/j.aim.2018.05.029zbMath1397.82013arXiv1611.00814OpenAlexW2548129158WikidataQ59459996 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

zbMATH Keywords

phase transitionsrandom graphsGibbs measuresstochastic block modelcavity methodbelief propagationinformation theoretic thresholdsrandom graph coloring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Phase transitions (general) in equilibrium statistical mechanics (82B26) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Coloring of graphs and hypergraphs (05C15) Statistical mechanics of magnetic materials (82D40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (40)

Phase transitions in discrete structures ⋮ The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models ⋮ Storage capacity in symmetric binary perceptrons ⋮ Strong replica symmetry in high-dimensional optimal Bayesian inference ⋮ Information theoretic limits of learning a sparse rule ⋮ An information-percolation bound for spin synchronization on general graphs ⋮ Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation ⋮ Counting colorings of triangle-free graphs ⋮ Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems ⋮ Lower bounds on the chromatic number of random graphs ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ Combinatorial statistics and the sciences ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Concentration of multi-overlaps for random dilute ferromagnetic spin models ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Mutual information for the sparse stochastic block model ⋮ Metastability of the Potts ferromagnet on random regular graphs ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Multi-variate correlation and mixtures of product measures ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ Bethe states of random factor graphs ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Fundamental limits of symmetric low-rank matrix estimation ⋮ Charting the replica symmetric phase ⋮ Charting the replica symmetric phase ⋮ Community Detection and Stochastic Block Models ⋮ The satisfiability threshold for random linear equations ⋮ Spin systems on Bethe lattices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference ⋮ On the computational tractability of statistical estimation on amenable graphs ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ The number of solutions for random regular NAE-SAT ⋮ The Cut Metric for Probability Distributions ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Marginals of a spherical spin Glass model with correlated disorder ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ The rank of sparse random matrices

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

This page was built for publication: Information-theoretic thresholds from the cavity method