Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Variations on Max-Product: Convergence and Correctness

Prof. Sekhar Tatikonda

The max-product algorithm is a simple message-passing scheme for computing the maximum assignment of a function defined on a factor graph. The algorithm has been successfully applied in many areas including problems in combinatorial optimization and the decoding of error-correcting codes. Even with these successes the max-product algorithm is not fully understood. The max-product algorithm may not converge and, even if it does, it is not guaranteed to produce the optimal assignment. In this talk, we present a simple derivation of a new family of message passing algorithms with strong guarantees on convergence and correctness.

This is joint work with Nick Ruozzi.

Problems with this site should be emailed to