Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems

DOI10.1007/11830924_32MaRDI QIDQ3595409zbMATH OpenOpenAlexFDO

Authors 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

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

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.

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

Cited in

(12)

• A Spectral Method for MAX2SAT in the Planted Solution Model
• Complete convergence of message passing algorithms for some satisfiability problems
• Why almost all k-colorable graphs are easy to color
• Convergence and correctness of belief propagation for the Chinese postman problem
• Perturbed message passing for constraint satisfaction problems
• Convergence of warning propagation algorithms for random satisfiable instances
• Convergence analysis of belief propagation algorithm for satisfiability problem
• On the random satisfiable process
• An Ising model inspired extension of the product-based MP framework for SAT
• Message passing for the coloring problem: Gallager meets Alon and Kahale
• Message passing algorithms for MLS-3LIN problem
• Message passing algorithms for MLS-3LIN problem

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)