Information-theoretic thresholds from the cavity method

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

zbMATH Keywords

phase transitions; random graphs; Gibbs measures; stochastic block model; cavity method; belief propagation; information theoretic thresholds; random graph coloring

Mathematics Subject Classification ID

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

Phase transitions in theq-coloring of random hypergraphs, Community Detection and Stochastic Block Models, Charting the replica symmetric phase, Unnamed Item, Unnamed Item, The Cut Metric for Probability Distributions, The replica symmetric phase of random constraint satisfaction problems, The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models, Storage capacity in symmetric binary perceptrons, Information theoretic limits of learning a sparse rule, Multi-variate correlation and mixtures of product measures, The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, The rank of sparse random matrices, Counting colorings of triangle-free graphs, Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems, 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, 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 discrete structures, 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, Fundamental limits of symmetric low-rank matrix estimation, Charting the replica symmetric phase, The satisfiability threshold for random linear equations, Spin systems on Bethe lattices, On the computational tractability of statistical estimation on amenable graphs, The number of solutions for random regular NAE-SAT, Marginals of a spherical spin Glass model with correlated disorder, Strong replica symmetry in high-dimensional optimal Bayesian inference, Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation, Concentration of multi-overlaps for random dilute ferromagnetic spin models, The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference, An information-percolation bound for spin synchronization on general graphs, Lower bounds on the chromatic number of random graphs

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