Information, Physics, and Computation

by Mézard, Marc; Montanari, Andrea

• ISBN13: 9780198570837
• ISBN10: 019857083X
• Format: Hardcover
• Copyright: 2009-03-27
• Publisher: Oxford University Press

Summary

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, adopting 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.

Author Biography

Professor Marc Mezard
CNRS Research Director at Universite de Paris Sud and Professor at Ecole Polytechnique, France
Marc Mezard received his PhD in 1984. He was hired in CNRS in 1981 and became research director in 1990 at Ecole Normale Superieure. He joined the Universite Paris Sud in 2001. He spent extensive periods in Rome University, in the KITP (Santa Barbara) and in MSRI (Berkeley). Author of about 150 publications, he has been
awarded the silver medal of CNRS in 1990 and the Ampere price of the French academy of science in 1996. Dr Andrea Montanari
Assistant Professor, Stanford University and CNRS France
Andrea Montanari received a Laurea degree in Physics in 1997, and a Ph. D. in Theoretical Physics in 2001 (both from Scuola Normale Superiore in Pisa, Italy). He has been post-doctoral fellow at Laboratoire de Physique Theorique de l'Ecole Normale Superieure (LPTENS), Paris, France, and the Mathematical Sciences Research Institute, Berkeley, USA. Since 2002 he is Charge de Recherche (a permanent research position with Centre National de la Recherche Scientifique, CNRS) at LPTENS.
In September 2006 he joined Stanford University as Assistant Professor in the Departments of Electrical Engineering and Statistics.
In 2006 he was awarded the CNRS bronze medal for theoretical physics.

Table of Contents

Independence
The random energy model	p. 93
Definition of the model	p. 93
Thermodynamics of the REM	p. 94
The condensation phenomenon	p. 100
A comment on quenched and annealed averages	p. 101
The random subcube model	p. 103
Notes	p. 105
The random code ensemble	p. 107
Code ensembles	p. 107
The geometry of the random code ensemble	p. 110
Communicating over a binary symmetric channel	p. 112
Error-free communication with random codes	p. 120
Geometry again: Sphere packing	p. 123
Other random codes	p. 126
A remark on coding theory and disordered systems	p. 127
Appendix: Proof of Lemma 6.2	p. 128
Notes	p. 128
Number partitioning	p. 131
A fair distribution into two groups?	p. 131
Algorithmic issues	p. 132
Partition of a random list: Experiments	p. 133
The random cost model	p. 136
Partition of a random list: Rigorous results	p. 140
Notes	p. 143
Introduction to replica theory	p. 145
Replica solution of the random energy model	p. 145
The fully connected p-spin glass model	p. 155
Extreme value statistics and the REM	p. 163
Appendix: Stability of the RS saddle point	p. 166
Notes	p. 169
Models on Graphs
Factor graphs and graph ensembles	p. 173
Factor graphs	p. 173
Ensembles of factor graphs: Definitions	p. 180
Random factor graphs: Basic properties	p. 182
Random factor graphs: The giant component	p. 187
The locally tree-like structure of random graphs	p. 191
Notes	p. 194
Satisfiability	p. 197
The satisfiability problem	p. 197
Algorithms	p. 199
Random K-satisfiability ensembles	p. 206
Random 2-SAT	p. 209
The phase transition in random K(>q; 3)-SAT	p. 209
Notes	p. 217
Low-density parity-check codes	p. 219
Definitions	p. 220
The geometry of the codebook	p. 222
LDPC codes for the binary symmetric channel	p. 231
A simple decoder: Bit flipping	p. 236
Notes	p. 239
Spin glasses	p. 241
Spin glasses and factor graphs	p. 241
Spin glasses: Constraints and frustration	p. 245
What is a glass phase?	p. 250
An example: The phase diagram of the SK model	p. 262
Notes	p. 265
Bridges: Inference and the Monte Carlo method	p. 267
Statistical inference	p. 268
The Monte Carlo method: Inference via sampling	p. 272
Free-energy barriers	p. 281
Notes	p. 287
Short-Range Correlations
Belief propagation	p. 291
Two examples	p. 292
Belief propagation on tree graphs	p. 296
Optimization: Max-product and min-sum	p. 305
Loopy BP	p. 310
General message-passing algorithms	p. 316
Probabilistic analysis	p. 317
Notes	p. 325
Decoding with belief propagation	p. 327
BP decoding: The algorithm	p. 327
Analysis: Density evoluation	p. 329
BP decoding for an erasure channel	p. 342
The Bethe free energy and MAP decoding	p. 347
Notes	p. 352
The assignment problem	p. 355
The assignment problem and random assignment ensembles	p. 356
Message passing and its probabilistic analysis	p. 357
A polynomial message-passing algorithm	p. 366
Combinatorial results	p. 371
An exercise: Multi-index assignment	p. 376
Notes	p. 378
Ising models on random graphs	p. 381
The BP equations for Ising spins	p. 381
RS cavity analysis	p. 384
Ferromagnetic model	p. 386
Spin glass models	p. 391
Notes	p. 399
Long-Range Correlations
Linear equations with Boolean variables	p. 403
Definitions and general remarks	p. 404
Belief propagation	p. 409
Core percolation and BP	p. 412
The Sat-Unsat threshold in random Xorsat	p. 415
The Hard-Sat phase: Clusters of solutions	p. 421
An alternative approach: The cavity method	p. 422
Notes	p. 427
The 1RSB cavity method	p. 429
Beyond BP: Many states	p. 430
The 1RSB cavity equations	p. 434
A first application: Xorsat	p. 444
The special value x=1	p. 449
Survey propagation	p. 453
The nature of 1RSB phases	p. 459
Appendix: The SP(y) equations for Xorsat	p. 463
Notes	p. 465
Random K-satisfiability	p. 467
Belief propagation and the replica-symmetric analysis	p. 468
Survey propagation and the 1RSB phase	p. 474
Some ideas about the full phase diagram	p. 485
An exercise: Colouring random graphs	p. 488
Notes	p. 491
Glassy states in coding theory	p. 493
Local search algorithms and metastable states	p. 493
The binary erasure channel	p. 500
General binary memoryless symmetric channels	p. 506
Metastable states and near-codewords	p. 513
Notes	p. 515
An ongoing story	p. 517
Gibbs measures and long-range correlations	p. 518
Higher levels of replica symmetry breaking	p. 524
Phase structure and the behaviour of algorithms	p. 535
Notes	p. 538
Symbols and notation	p. 541
Equivalence relations	p. 541
Orders of growth	p. 542
Combinatorics and probability	p. 543
Summary of mathematical notation	p. 544
Information theory	p. 545
Factor graphs	p. 545
Cavity and message-passing methods	p. 545
References	p. 547
Index	p. 565
Table of Contents provided by Ingram. All Rights Reserved.