Campus Event Calendar
Event Entry
What and Who
Message Passing Algorithms
Megha Khosla
International Max Planck Research School for Computer Science - IMPRS
PhD Application Talk
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 19 October 2009
09:00
240 Minutes
E1 4
024
Saarbrücken
Abstract
Constraint Satisfaction Problems (CSPs) are defined over a set of variables whose state must satisfy a number of constraints. We study a class of algorithms called Message Passing Algorithms which aim at finding the probability distribution of the variables over the space of satisfying assignments. These algorithms involve passing local messages over the edges of a factor graph constructed corresponding to the CSP. We focus on Belief Propagation algorithm which finds exact solution marginals for tree-like factor graphs. However, convergence and exactness cannot be guaranteed for a general factor graph. We propose a method for improving BP to account for cycles in the factor graph. We also study another message passing algorithm known as Survey Propagation which is empirically quite effective in solving random K-SAT problem even with densities close to satisfiability threshold. We do a thorough theoretical analysis of the performance of such algorithms which are less understood in practice. This, we believe is helpful in designing newer algorithms on similar lines for hard combinatorial problems.
Contact
--email hidden
passcode not visible
logged in users only
Jennifer Gerling, 10/07/2009 17:07
Heike Przybyl, 10/07/2009 16:18 -- Created document.
Heike Przybyl, 10/07/2009 16:18 -- Created document.