Unified survey-belief propagation approach for satisfiability
published: Feb. 25, 2007, recorded: January 2005, views: 3733
Report a problem or upload filesIf 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.
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 pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !