Spring 2008 Seminar Series

DATE: December 11
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the ORC ConferenceRoom, E40-106

SPEAKER:
Christian Borgs

TITLE
Belief Propagation for weighted b-matchings

ABSTRACT
Despite the spectacular success of belief propagation algorithms in many application areas, theoretical results concerning both the correctness and convergence of these algorithms are known in very few cases, most of which concern graphs with at most one cycle, or graphs whose cycles become longer and longer with the size of the graphs. In this talk I present joint work with Mohsen Bayati, Jennifer Chayes and Riccardo Zecchina, in which we consider weighted b-matchings on arbitrary input graphs. We show that belief propagation converges to the correct solution in finite time, provided the linear programming relaxation of the problem has no fractional solutions.