Mathematical Digest

Short Summaries of Articles about Mathematics
in the Popular Press

"Passing Messages Between Disciplines," by Marc Mézard. Science, 19 September 2003,pages 1685-1686.

The disciplines in this case are physics and computer science---applied toerror-correcting codes---but there is some mathematics in this article. Someerror-correcting systems work in theory but have been impractical to implement.A technique called belief propagation can make decoding procedures workfaster so that they are practical. Mézard writes about how beliefpropagation procedures are applied to the satisfiability problem (whether thereexist truth values for a set of Boolean variables so that given constraints aresatisfied). Satisfiability has a critical value, separating problems that arealmost always satisfiable from those that are almost never satisfiable.Statistical physics helps to understand the phase transition between the twoopposite regions of problems, which helps improve belief propagationprocedures.

--- Mike Breen