Probabilistic Analysis of Message Passing Algorithms

Andrea Montanari
Department of Electrical Engineering
Stanford University


Wednesday, November 15, 2006
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

Random sparse graphical models appear in a variety of contexts, ranging from communications to combinatorics and statistical mechanics. An increasingly sophisticated theory has been developed to analyze message passing algorithms (such as belief propagation) in such problems. This analysis plays a double role: (i) It opens the way to the design/optimization of these systems; (i) It provides a new array of proof techniques to deal with difficult mathematical problems.

I will review these developments working out one particular example: belief propagation-based multi-user detection.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html