Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems

DOI10.1007/11830924_32zbMath1155.68507arXiv0812.0147OpenAlexW2139919528MaRDI QIDQ3595409

Elchanan Mossel, Dan Vilenchik, Uriel Feige

Publication date: 28 August 2007

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0812.0147

Mathematics Subject Classification ID

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

Related Items (4)

A Spectral Method for MAX2SAT in the Planted Solution Model ⋮ On the Random Satisfiable Process ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ Convergence and correctness of belief propagation for the Chinese postman problem

This page was built for publication: Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems