Princeton-Rutgers Seminar Series in Communications and Information Theory

Chris Rose and Sergio Verdú, Co-Chairs

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


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.