Statistical Physics for Communication and Computer Science

 

Instructor Ruediger Urbanke
Office INR 116
Phone +4121 6937692
Email ruediger.urbanke@epfl.ch
Office Hours By appointment

and

Instructor Nicolas Macris
Office INR 134
Phone +4121 6938114
Email nicolas.macris@epfl.ch
Office Hours By appointment

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

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

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 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).

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).
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%

Scribing

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