Marc Mézard, LPTMS Orsay

Information, Physics, and Computation (13.5h)

It has been realized in recent years that statistical physics of strongly disordered and interacting systems is deeply related to some crucial aspects of information theory and optimization. This course aims at introducing to this rich topic, focusing on the common concepts and methods appearing, often under different disguises, in physics and in computer science.

1. Background.

Introduction to information theory: entropy, mutual information, data compression, data transmission and channels, error-correcting codes • Introduction to combinatorial optimization and to computational complexity classes (P, NP, NP-complete) • Short survey on spin glasses

2. Independent configurations

Random energy model: the condensation phenomenon • Random code ensemble and Shannon’s theorem

3. Models on graphs

Factor graphs and graph ensembles • Phase transitions in graph geometry • Models on graphs: LDPC error correcting codes

4. Message passing, belief propagation and the cavity method

Belief propagation (BP) equations • Statistical analysis of messages and the replica symmetric cavity method • Applications to coding and to spin glass theory

5. Replica symmetry breaking in the cavity method

The glassy state • Metastability and the multiplicity of solutions to BP equations • Statistical analysis of the many solutions • Applications to K-satisfiability