A spectral approach to analysing belief propagation for 3-colouring

DOI10.1017/S096354830900981XzbMATH Open1191.05084OpenAlexW3103376245MaRDI QIDQ3557516FDOQ3557516

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

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

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)

Cites Work

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

Cited In (8)

• 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
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• The solution space structure of planted constraint satisfaction problems with growing domains
• The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
• Message passing algorithms for MLS-3LIN problem

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)