The Surprising Power of Randomness in Belief Propagation.

Thursday, March 19, 2015 - 10:20am - 11:00am
Klaus 1116
Elchanan Mossel (University of California, Berkeley)
Abstract: Belief Propagation is a very efficient and popular algorithm for inference.
While it is long known that the algorithm is exact for trees, its applicability for non-tree graphs have
been intensively studied in coding theory, statistical physics and theoretical computer science for the last few decades. I will present the algorithm and some old and newer theoretical guarantees for its performance. Some of the new results highlight the role of randomness in applying the algorithm and lead to a more efficient and derandomized versions of the algorithm.