Unified survey-belief propagation approach for satisfiability

author: Marco Pretti, Politecnico di Torino
published: Feb. 25, 2007,   recorded: January 2005,   views: 3733

See Also:

Download slides icon Download slides: oiml05_pretti_usbpa_01.pdf (152.9┬áKB)

Help icon Streaming Video Help

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


In this talk I shall discuss a modified message-passing BP (Belief Propagation) procedure, which can be generally used to minimize variational Bethe free energies in statistical physics. By a straightforward mapping, this algorithm can be easily applied to combinatorial optimization problems, such as 3-satisfiability, the prototype of NP-hard problems. I show that the method can be also extended to the framework of SP (Survey Propagation), a recently proposed algorithm which, still making use of techniques borrowed from statistical physics, overcomes problems encountered by local search algorithms on hard instances close to the ``SAT-UNSAT'' transition. This allows to obtain a unified and quite stable message passing scheme, which can be used both in the ``full replica-symmetry-breaking'' region, where ordinary Belief Propagation usually does not converge, and in the ``hard'' region near the sat-unsat transition, where it allows to solve subformulae generated by ``survey inspired decimation''.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 John Realpe, October 11, 2008 at 6:32 p.m.:

Hi all, I haven't been able to watch videos of this Workshop, is there a way to find them?


Write your own review or comment:

make sure you have javascript enabled or clear this field: