Complete convergence of message passing algorithms for some satisfiability problems

Details Complete convergence of message passing algorithms for some satisfiability problems Complete convergence of message passing algorithms for some satisfiability problems

2008-11-30

arxiv.org/abs/0812.0147v2

Mathematics

Probability

1 Figure. Minor revision of a previous version

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Complete convergence of message passing algorithms for some satisfiability problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complete convergence of message passing algorithms for some satisfiability problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complete convergence of message passing algorithms for some satisfiability problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54817