Passing Messages Between Disciplines

In today's Science Marc Mézard discusses the interaction between Computer Science and Computational Physics.

Problems in computer science, such as error correction in information transfer and "satisfiability" in optimization, show phase transitions familiar from solid-state physics. In his Perspective, Mézard explains how recent advances in these three fields originate in similar "message passing" procedures. The exchange of elaborate messages between different variables and constraints, used in the study of phase transitions in physical systems, helps to make error correction and satisfiability codes more efficient.

---

The author is in the Laboratoire de Physique Théorique et Modèles Statistiques, CNRS, and Université de Paris Sud, 91405 Orsay, France. E-mail: mezard@lptms.u-psud.fr

The following diagram from the article shows how message passing help solves the error correction problem.

The circles represent the bits transmitted through the channel. The squares are the parity check constraints; for instance, constraint C1 requires that the sum of bits B1, B2, B3, and B5 should be even. Along each edge of this graph two messages are exchanged, one in each direction. These messages give the "belief" of the sending node on the state of the bit. This retrieves the actual value quickly for low density error correcting codes that are not too close to the Shannon limit. This also can be used to solve N-Satisfiability problems again when they are not too close to the Shannon limit.

By studying spin glasses, it has been discovered that these algorithms do not do well when the solutions are not clustered. The belief messages are limited to local areas. So, the algorithm has been modified to pass not just a beliefs but a whole survey of beliefs to get around the local problem. This has allowed this algorithm to be used for noisier channels and more difficult optimization problems.