|
 |
"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 to error-correcting codes---but there is some mathematics in this article. Some error-correcting systems work in theory but have been impractical to implement. A technique called belief propagation can make decoding procedures work faster so that they are practical. Mézard writes about how belief propagation procedures are applied to the satisfiability problem (whether there exist truth values for a set of Boolean variables so that given constraints are satisfied). Satisfiability has a critical value, separating problems that are almost always satisfiable from those that are almost never satisfiable. Statistical physics helps to understand the phase transition between the two opposite regions of problems, which helps improve belief propagation procedures.
--- Mike Breen
 |
Comments: Email Webmaster |
