Statistical physics for communication and computer science

Instructor Nicolas Macris and Ruediger Urbanke
Office INR 134
Phone +4121 6938114
Email and
Office Hours By appointment


Lectures: Wednesdays 12h15 – 14h00, room BC02

Language: English

ECTS Crédits: 4, exam form: project.

The aim of the course is to introduce the student to those fundamental notions of statistical physics which have found applications in communications, signal processing 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, compressed sensing and the random constraint satisfaction problem. 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 plan:
Part I: Models.

1. Models and Questions: Codes, Compressive Sensing and Satisfiability.
2. A few notions of statistical physics.
3. Formulation of coding, compressed sensing, satisfiability as spin-glasses.
4. The Curie-Weiss model and phase transitions.

Part II: Message passing algorithms.

5. Marginalization, Sum-Product and Belief Propagation.
6. Coding: belief propagation and density evolution.
7. Interlude: BP to TAP for the Sherrington-Kirkpatrick spin-glass.
8. Compressive sensing: Approximate message passing and state evolution.
9. Random K-sat: BP guided decimation.

Part III: Advanced topics.

10. The Bethe free energy and the replica symmetric formulas.
11. The Maxwell construction.
12. Spatial coupling and nucleation.
13. The cavity method and application to K-sat.
14. Random K-sat: survey propagation guided decimation.

We have a set of notes in progress on which we work on. This statphys.pdf will be updated weekly to the most recent version.

Tentative Weekly Program


Date Topic Assignment   Due Date   Remarks
Feb 22 and Feb 29 Models and questions: coding, compressed sensing, K-sat (chap 1)  hmw1.pdf   always two weeks later    
March 8 Stat mech basic principles (chap 2)  hmw2.pdf        
March 15 and 22 Reformulation of coding and compressed sensing as spin glasses (chap 3)  hmw3.pdf        
March 29 Curie-Weiss model: exact solution (chap 4)  hmw4.pdf        
April 5 Marginalization, Belief Propagation (chap 5)  hmw5.pdf        
April 12 Application to coding and Density evolution (chap 6)  hmw6.pdf      
April 19 Easter Break        
April 26

BEC: coding and density evolution (chap 6)

May 3 Compressive sensing: AMP algo (chap 8)  hmw7.pdf      
May 10 Compressed sensing:state evolution and Donoho-Tanner transition curve (chap 8)  hmw8.pdf        
May 17 Bethe free energy (chap 11)          
May 24 Replica solution, potential function, Maxwell construction (chap 12)          
May 31 Spatial coupling: review (chap 13)          
Final Project Binary rank-one matrix factorization  project.pdf        

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% for half of weekly assignments (among your choice)
final project 70%  
—————————- ——-  
total 100%  

return to courses main menu