The AMS website will be down for maintenance on October 25th between 6:00pm - 10:00pm ET. This downtime includes registration for the 2019 JMM MEETING in Baltimore. We apologize for any inconvenience this may cause. For questions please contact AMS Customer Service at email@example.com or (800) 321-4267 (U.S. & Canada), (401) 455-4000 (Worldwide).
"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