A Spectral Approach to Analysing Belief Propagation for 3-Colouring

DOI10.1017/S096354830900981XzbMath1191.05084OpenAlexW3103376245MaRDI QIDQ3557516

Amin Coja-Oghlan, Dan Vilenchik, Elchanan Mossel

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) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Belief propagation for the maximum-weight independent set and minimum spanning tree problems ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ Message passing algorithms for MLS-3LIN problem ⋮ Spectral redemption in clustering sparse networks ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Convergence and correctness of belief propagation for the Chinese postman problem ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Lifts, discrepancy and nearly optimal spectral gap
• Uniqueness of uniform random colorings of regular trees
• Sparse quasi-random graphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Efficient erasure correcting codes
• Design of capacity-approaching irregular low-density parity-check codes
• Survey propagation: An algorithm for satisfiability
• Gibbs states and the set of solutions of random constraint satisfaction problems

This page was built for publication: A Spectral Approach to Analysing Belief Propagation for 3-Colouring