Statistical Physics for Communication and Computer Science
COM-712 / 4 credits
Teacher(s): Urbanke Rüdiger, Macris Nicolas
Language: English
Remark: Not offered this year
Summary
The course introduces the student to notions of statistical physics which have found applications in communications and computer science. We focus on graphical models with the emergence of phase transitions, and their relation to the behavior of efficient algorithms.
Content
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 (AMP) 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.
Keywords
Statistical physics, belief propagation, Bethe free energy, mean field method, coding, K-SAT, factor graph, cavity method, Ising model.
Learning Prerequisites
Recommended courses
Probability, calculus;
In the programs
- Exam form: Multiple (session free)
- Subject examined: Statistical Physics for Communication and Computer Science
- Lecture: 28 Hour(s)
- Practical work: 28 Hour(s)