- français
- English
Coursebooks
Statistical Physics for Communication and Computer Science
COM-712
Lecturer(s) :
Macris NicolasUrbanke Rüdiger
Language:
English
Remark
Next Time: Postponed to Spring 2022Summary
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;
Resources
Websites
In the programs
- Semester
- Exam form
Multiple - Credits
4 - Subject examined
Statistical Physics for Communication and Computer Science - Lecture
28 Hour(s) - Practical work
28 Hour(s)
- Semester
Reference week
legend
- Autumn semester
- Winter sessions
- Spring semester
- Summer sessions
- Lecture in French
- Lecture in English
- Lecture in German