Statistical Physics for Communication and Computer Science

Instructor Nicolas Macris
Office INR 134
Phone +4121 6938114
Email [email protected]
Office Hours By appointment

and

Instructor Ruediger Urbanke
Office INR 116
Phone +4121 6937692
Email [email protected]
Office Hours By appointment

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 22 Spatial Coupling final-project.pdf July 2
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

graded homeworks 30%
final project 70%
—————————- ——-
total 100%

return to courses main menu