and
Lectures: Wednesdays 13h15 – 15h00, room INF213
Language: English
ECTS Crédits: 4, exam form: project.
Description
The aim of the course is to introduce the student to those fundamental notions of statistical physics which have found applications in communications and computer science. The course will focus on systems which can be described by means of an underlying graphical model. These include in particular modern coding systems, the random constraint satisfaction problem and compressed sensing. We will be interested in the behavior of such systems in the infinite size limit. In particular, we focus on the emergence of phase transitions, how they can be analyzed, and how they relate to the behavior of efficient algorithms.
The students may choose to study more deeply one or the other of the topics discussed in class, as well as recent research directions, through a term project.
Tentative topics:
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 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.
Notes:
This course was taught for the first time in 2010/11. We have a sparse set of notes which you can find here. We will expand them during this semester and statphys.pdf is always the latest version.
Detailed Schedule
| Date |
Topic |
Assignment |
Due Date |
Remarks |
| Feb 20 |
models and questions |
hw1.pdf |
Feb. 27 |
UCP-prob.pdf |
| Feb 27 |
stat mech principles —- |
hw2.pdf |
Mar. 6 |
|
| Mar 6 |
reformulation of models – |
hw3.pdf |
Mar.13 |
|
| Mar 13 |
Curie Weiss model —— |
hw4.pdf |
Mar.20 |
|
| Mar 30 |
marginalization and BP- |
hw5.pdf |
Mar.27 |
|
| Mar 27 |
coding: Belief Propagation |
hw6.pdf |
Apr.10 |
|
| Apr 3 |
Easter break (Mar29 – Apr7) |
| Apr 10 |
coding: Density Evolution |
hw7.pdf |
Apr.17 |
|
| Apr 17 |
SK model: from BP to TAP |
hw8.pdf |
Apr.24 |
|
| Apr 24 |
Compressive sensing: from BP to AMP |
hw9.pdf |
May.1 |
|
| May 1 |
Compressive sensing: State evolution |
hw10.pdf |
May. 8 |
|
| May 8 |
Random K SAT: Wormald method |
hw11.pdf |
May. 15 |
|
| May 15 |
Maxwell construction |
hw12.pdf |
May. 22 |
|
| May 29 |
Variational methods: Bethe and replica symmetric energies/entropies |
Bibliography:
Statistical Physics of Spin Glasses and Information Processing, by H. Nishimori, Oxford University Press, (2001).
Information Theory, Inference and Algorithms, by D. J. C. MacKay, Cambridge University Press (2003).
New Optimization Algorithms in Physics, Edited by A. K. Hartmann and H. Rieger, Wiley (2004).
Modern Coding Theory, by T. Richardson and R. Urbanke, Cambridge University Press, (2008).\ Information, Physics and Computation, by M. Mezard and A. Montanari, Oxford Graduate Texts, (2009).
Exams and Grading
