Jump to ContentJump to Main Navigation
Information, Physics, and Computation - Oxford Scholarship Online
Users without a subscription are not able to see the full content.

Information, Physics, and Computation

Marc Mézard and Andrea Montanari


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

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


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