Coursebooks

Statistical Physics for Communication and Computer Science

COM-712

Lecturer(s) :

Macris Nicolas
Urbanke Rüdiger

Language:

English

Remarque

Next Time: Spring 2021

Summary

The course introduces the student to notions of statistical physics which have found applications in communications and computer science. We focus on graphical models with the emergence of phase transitions, and their relation to the behavior of efficient algorithms.

Content

1. Models and Questions: Codes, Satisfiability, and Compressive Sensing.
2. Notions of statistical physics: free energy, phase transitions, pure states.
3. Exactly solvable models ¿ the Curie-Weiss model and Ising on a tree.
4. Statistical mechanical formulation of coding, K-sat and compressed sensing.
5. Marginalization, Sum-Product and Belief Propagation.
6. Application to LDPC codes.
7. Density evolution analysis. Maxwell construction and conjecture.
8. Approximate Message Passing (AMP) for compressed sensing.
9. State evolution analysis of AMP.
10. Random K-sat: Unit Clause Propagation and Wormald's method.
11. Belief Propagation guided decimation for K-sat.
12. Variational formulation of Belief Propagation: the Bethe free energy.
13. The cavity method. Dynamical, condensation and sat-unsat phase transitions.
14. The phase diagram of K-sat. Survey Propagation guided decimation.

Keywords

Statistical physics, belief propagation, Bethe free energy, mean field method, coding, K-SAT, factor graph, cavity method, Ising model.

Learning Prerequisites

Recommended courses

Probability, calculus;

Resources

Websites

• http://ipg.epfl.ch/doku.php?id=en:courses:2014-2015:statphys