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.
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
Random energy model: the condensation phenomenon • Random code ensemble and Shannon’s theorem
Factor graphs and graph ensembles • Phase transitions in graph geometry • Models on graphs: LDPC error correcting codes
Belief propagation (BP) equations • Statistical analysis of messages and the replica symmetric cavity method • Applications to coding and to spin glass theory
The glassy state • Metastability and the multiplicity of solutions to BP equations • Statistical analysis of the many solutions • Applications to K-satisfiability