Title: Belief Propagation on Partially Ordered Sets
Speaker: Robert J. McEliece, Professor of Electrical Engineering, California Institute of Technology
Date: Thursday March 13, 2003, 4:30-5:30 pm
Location: Princeton University, Friend 006
Abstract:
The field of error-correcting codes has been revolutionized by the advent of suboptimal iterative decoding methods, for example turbo-decoding and iterative decoding of low-density parity-check (LDPC) codes. Several years ago it was recognized that all such decoding algorithms are special cases of Judea Pearl's "belief propagation" algorithm applied to graphs with cycles, although BP isn't supposed to work when cycles are present! In this talk I will, motivated by some recent work of Yedidia, Freeman, and Weiss, introduce a promising generalization of BP in which the messages are passed not along the edges of a graph, but rather along the edges of the Hasse diagram of a finite partially ordered set. This generalization of BP can in principle be used to solve, either exactly or approximately, a wide variety of problems from engineering, physics, and computer science. Seminar Sponsored by DIMACS Special Focus on Computational Information Theory and Coding.