### 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

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.