Marc Mézard - Böcker

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. It is accessible to graduate students and researchers without a specific training in any of these fields. The selected topics include spin glasses, error correcting codes, satisfiability, and are central to each field. The approach focuses on large random instances and adopts a common probabilistic 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 study phase transitions.

About sixty years ago, the anomalous magnetic response of certain magnetic alloys drew the attention of theoretical physicists. It soon became clear that understanding these systems, now called spin glasses, would give rise to a new branch of statistical physics. As physical materials, spin glasses were found to be as useless as they were exotic. They have nevertheless been recognized as paradigmatic examples of complex systems with applications to problems as diverse as neural networks, amorphous solids, biological molecules, social and economic interactions, information theory and constraint satisfaction problems.This book presents an encyclopaedic overview of the broad range of these applications. More than 30 contributions are compiled, written by many of the leading researchers who have contributed to these developments over the last few decades. Some timely and cutting-edge applications are also discussed. This collection serves well as an introduction and summary of disordered and glassy systems for advanced undergraduates, graduate students and practitioners interested in the topic.