Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems

DOI10.1007/11830924_32zbMATH Open1155.68507arXiv0812.0147OpenAlexW2139919528MaRDI QIDQ3595409FDOQ3595409

Elchanan Mossel, Uriel Feige, Dan Vilenchik

Publication date: 28 August 2007

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

Abstract: In this paper we analyze the performance of Warning Propagation, a popular message passing algorithm. We show that for 3CNF formulas drawn from a certain distribution over random satisfiable 3CNF formulas, commonly referred to as the planted-assignment distribution, running Warning Propagation in the standard way (run message passing until convergence, simplify the formula according to the resulting assignment, and satisfy the remaining subformula, if necessary, using a simple "off the shelf" heuristic) results in a satisfying assignment when the clause-variable ratio is a sufficiently large constant.

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

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
• A new look at survey propagation and its generalizations
• Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios

Mathematics Subject Classification ID

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

Cited In (5)

• A Spectral Method for MAX2SAT in the Planted Solution Model
• Why almost all \(k\)-colorable graphs are easy to color
• Convergence and correctness of belief propagation for the Chinese postman problem
• Message passing for the coloring problem: Gallager meets Alon and Kahale
• On the Random Satisfiable Process

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 Q3595409)