Statistical Physics for Communication and Computer Science

InstructorRuediger Urbanke
OfficeINR 116
Phone+4121 6937692
Office HoursBy appointment


InstructorNicolas Macris
OfficeINR 134
Phone+4121 6938114
Office HoursBy appointment

Lectures: Thursday 09:15 - 11:00 (Room: INR113) NO CHANGE OF TIME !

Language: English
ECTS Crédits: 4, exam form: term paper.

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 sparse graph. These include in particular modern coding systems and the constraint satisfaction problem. We will be interested in the behavior of such a system in the infinite size limit. In particular, we focus on the emergence of phase transitions and how they can be analyzed.

We will cover the following topics:

1. Models and questions. 2. Basic notions of statistical physics. 3. An exactly solvable model – The complete graph. 4. The factor graph approach to the marginalization on trees. 5. Belief propagation as an algorithm (coding, K-SAT). 6. Belief propagation as a mean field approach (Bethe free energy). 7. Discussion of validity of mean filed approach. 8. The cavity method (K-SAT).


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).
Information, Physics and Computation, by M. Mezard and A. Montanari, Oxford Graduate Texts, (2009).

Exams and Grading

graded homeworks 20%
scribing 10%
final project 70%
total 100%


Each week, we will ask one of you to take notes and to type them up. The finished typed up notes should be ready no later than one week after the lecture. We will post them on the web. Use the following scribe.tex template. Please send both, the tex files as well as a compiled pdf file to us.

Detailed Schedule

Date Topic Assignment Due Date/Solutions Posted Notes Remarks
Feb 24 models and questions hw1.pdf lecture1
Mar 3 basic notions of statistical physics hw2.pdf equ (9) has been corrected. Thanks to Saeid ! lecture2
Mar 10 Ising model and solution for the complete graph hw3.pdf lecture3
Mar 17 stat phys formulation of coding hw4.pdf lecture4
Mar 24 factor graph approach: marginalisation on trees, message passing hw5.pdf MCT pages 49-70
Mar 31 Binary case, Gallager codes on the BEC, empirical behavior hw6.pdf lecture6.pdf
Apr 7 Analysis of BP algorithm for the BEC via density evolution no hw lecture7.pdf
Apr 14 BP guided decimation algorithm for K-SAT hw8.pdf lecture8.pdf
Apr 21 lower bound on threshold via Wormald method for UCP hw9.pdf wormald.pdf achlioptas.pdf
May 5 Bethe free energy, relation to BP hw10.pdf lecture10.pdf
May 12 Coding: conjectured replica symmetric formula, relating MAP and BP. hw11.pdf lecture11.pdf
May 19 1) Proof ideas of conjectures for BEC. 2) Beyond BP, the cavity method no hw lec12BEC.pdf lec12cavity.pdf
May 26 Survey Propagation for K-SAT project.pdf lecture13.pdf Due Date: June 23rd

return to courses main menu

Last modified:: %2011/%08/%18 %16:%Aug