| Instructor | Ruediger Urbanke |
| Office | INR 116 |
| Phone | +4121 6937692 |
| [email protected] | |
| Office Hours | By appointment |
and
| Instructor | Nicolas Macris |
| Office | INR 134 |
| Phone | +4121 6938114 |
| [email protected] | |
| 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 | |