Fiches de cours 2017-2018

PDF
 

Statistical Physics for Communication and Computer Science

COM-712

Lecturer(s) :

Macris Nicolas
Urbanke Rüdiger

Language:

English

Frequency

Every 2 years

Remarque

Next Time: Spring 2019

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;

Resources

Websites

In the programs

  • Computer and Communication Sciences (edoc), 2017-2018
    • Semester
    • Exam form
      Multiple
    • Credits
      4
    • Subject examined
      Statistical Physics for Communication and Computer Science
    • Lecture
      28 Hour(s)
    • Practical work
      28 Hour(s)

Reference week

Lecture
Exercise, TP
Project, other

legend

  • Autumn semester
  • Winter sessions
  • Spring semester
  • Summer sessions
  • Lecture in French
  • Lecture in English
  • Lecture in German