Complete convergence of message passing algorithms for some satisfiability problems

DOI10.4086/TOC.2013.V009A019MaRDI QIDQ3191589zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel, Dan Vilenchik, Uriel Feige

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2013.v009a019

zbMATH Keywords

constraint satisfactionSATstatistical physicsaverage case

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40)

Recommendations

• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• Convergence of warning propagation algorithms for random satisfiable instances
• Survey propagation: An algorithm for satisfiability
• Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
• A new look at survey propagation and its generalizations

Cites work

• Design of capacity-approaching irregular low-density parity-check codes
• The decimation process in random \(k\)-SAT

Cited in

(7)

• Solving non-uniform planted and filtered random SAT formulas greedily
• On the interpolation between product-based message passing heuristics for SAT
• Convergence of warning propagation algorithms for random satisfiable instances
• Convergence analysis of belief propagation algorithm for satisfiability problem
• An Ising model inspired extension of the product-based MP framework for SAT
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• Message passing for the coloring problem: Gallager meets Alon and Kahale

This page was built for publication: Complete convergence of message passing algorithms for some satisfiability problems

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