course: Large random systems: from coding to optimization and statistical mechanics
speaker: Andrea Montanari (LPTENS)abstract: (1) Codes on graphs as a Markov Random Field. Examples of Markov Random Fields from combinatorial optimizationdecision problems, and statistical mechanics. Factor graph description. Free energy and Gibbs free energy. Threshold phenomena (phase transitions).
(2) A toy model: the ferromagnetic Ising model on random graphs. Belief propagation as an algorithm for computing marginals. Belief propagation as a proof technique. Bethe free energy.
(3) Phase diagram of LDPC ensembles. GEXIT functions, and generalized area theorems. The threshold for MAP (Maximum a Posteriori Probability) decoding.
(4) continuation from the previous lecture if necessary Solving large optimization problems through belief propagation: the example of independent sets.
(5) Proliferation of pure states. Algorithmic consequences.
(6) Dynamics. Local search algorithms: application (and analysis) for coding and optimization.
timetable:
Mon 30 Jan, 14:00 - 15:30, Aula Dini
Tue 31 Jan, 9:00 - 10:30, Aula Dini
Wed 1 Feb, 11:30 - 12:30, Aula Dini
Thu 2 Feb, 9:00 - 10:30, Aula Dini
Fri 3 Feb, 9:00 - 10:30, Aula Dini
Fri 3 Feb, 16:00 - 17:30, Aula Dini
<< Go back