Information, Physics, and Computation
Marc Mézard and Andrea Montanari
Abstract
This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and coding/information theory. The topics which have been selected, including spin glasses, error correcting codes, satisfiability, are central to each field. The approach focuses on the limit of large random instances, adopting a common formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfacti ... More
This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and coding/information theory. The topics which have been selected, including spin glasses, error correcting codes, satisfiability, are central to each field. The approach focuses on the limit of large random instances, adopting a common formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfaction solving. It also explains analysis techniques like density evolution and the cavity method, and uses them to derive phase diagrams and study phase transitions.
Keywords:
spin glasses,
error correcting codes,
constraint satisfaction,
satisfiability,
message passing,
belief propagation,
survey propagation,
cavity method,
density evolution,
phase transition
Bibliographic Information
| Print publication date: 2009 |
Print ISBN-13: 9780198570837 |
| Published to Oxford Scholarship Online: September 2009 |
DOI:10.1093/acprof:oso/9780198570837.001.0001 |
Authors
Affiliations are at time of print publication.
Marc Mézard, author
Laboratoire de Physique Théorique et Modeles Statistiques, Université de Paris Sud, Orsay, France
Andrea Montanari, author
Electrical Engineering and Statistics Department, Stanford University, USA
More
Less
