A spectral approach to analysing belief propagation for 3-colouring

DOI10.1017/S096354830900981XMaRDI QIDQ3557516zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Elchanan Mossel, Dan Vilenchik

Publication date 23 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s096354830900981x

zbMATH Keywords

random graphsgraph colouringbelief propagationspectral properties of graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Theory and Applications of Satisfiability Testing
• Local stability of belief propagation algorithm with multiple fixed points
• Convergence and correctness of belief propagation for the Chinese postman problem
• Belief propagation for graph partitioning
• Message passing for the coloring problem: Gallager meets Alon and Kahale

Cites work

• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Design of capacity-approaching irregular low-density parity-check codes
• Efficient erasure correcting codes
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Lifts, discrepancy and nearly optimal spectral gap
• Sparse quasi-random graphs
• Survey propagation: An algorithm for satisfiability
• Uniqueness of uniform random colorings of regular trees

Cited in

(9)

• Belief propagation for graph partitioning
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Convergence and correctness of belief propagation for the Chinese postman problem
• Spectral redemption in clustering sparse networks
• Belief propagation for the maximum-weight independent set and minimum spanning tree problems
• The Lovász theta function for random regular graphs and community detection in the hard regime
• The solution space structure of planted constraint satisfaction problems with growing domains
• Message passing algorithms for MLS-3LIN problem
• Decoding from pooled data: sharp information-theoretic bounds

This page was built for publication: A spectral approach to analysing belief propagation for 3-colouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557516)