Basser Seminar Series

Relations between linear programming, dynamic programming, and the min-sum algorithm

Speaker: Dr Guy Even
School of Electrical Engineering, Tel-Aviv University

Time: Wednesday 21 August 2010, 4:00-5:00pm
Refreshments will be available from 3:30pm

Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1

Add seminar to my diary


Decoding of error correcting codes is performed in mobile phones by special purpose hardware that executes a message passing algorithm called belief propagation. There are no rigorous proofs that fully explain the low decoding errors that are achieved in practice. In particular, there are no proven bounds on the decoding error when the number of iterations of the decoding algorithm is large and finite. This problem is often called loopy belief-propagation and has many applications in addition to error correcting codes.

We focus on a variant of belief-propagation called the min-sum algorithm (also known as the sum-product algorithm). The min-sum algorithm is interpreted as a dynamic programming algorithm over the computation tree of the graphical model. We use dynamic programming and graph covers to show connections between the min-sum algorithm and linear programming.

The study of relations between these algorithmic techniques is motivated by decoding of error correcting codes. Many variants of the min-sum algorithm have been proposed for decoding starting with Gallagher in 1963. Viterbi's algorithm from 1967 for decoding convolutional codes is a dynamic programming algorithm. Feldman, Karger, and Wainwright proposed in 2005 to use linear programming for decoding binary linear codes.

The talk will focus on two results:

  1. A proof that the min-sum algorithm for integer packing and covering problems is not better than linear programming.
  2. Inverse polynomial bounds on the decoding error for a wide class of error correcting codes with logarithmic girth (including LDPC codes, and irregular repeat-accumulate codes with both even and odd repetition factors). The bounds apply both to linear-programming decoding as well as a variant of the min-sum algorithm.

The talk assumes no prior acquaintance with error correcting codes, belief-propagation, and linear programming decoding.

Joint work with Nissim Halabi.

Speaker's biography

Guy Even received his B.Sc. degree in 1988 in Mathematics and Computer Science from the Hebrew University, and his M.Sc. and D.Sc. in Computer Science from the Technion in 1991 and 1994, respectively. Dr Even spent his post-doctorate in the University of the Saarland during 1995-1997 in Wolfgang Paul's group. Since 1997, he is a faculty member in the School of Electrical Engineering in Tel-Aviv University.

Dr Even is interested in algorithms and their applications in various fields. He has published papers on the theory of VLSI, approximation algorithms, computer arithmetic, online algorithms, frequency assignment in radio networks, scheduling problems, packet-routing, and decoding of error correcting codes. He is on the editorial board of "Theory of Computing Systems".

Together with his PhD student Moti Medina, Dr Even wrote a digital hardware textbook titled "Digital Logic Design: A Rigorous Approach" published in 2012 by Cambridge University Press.