Information, Physics and Computation

  • Pau Vilimelis Aceituno
A3 02 (Seminar room)


Statistical Physics, Information Theory and Combinatorial Optimization have many concepts in common: bits, complexities, large deviations or partition functions, are common, albeit for different questions. The goal of this course is to understand their intersections: How can an algorithm show a phase transition, what is computational complexity in terms of information. In order to keep it accessible, we will not go into detail in any of those fields, and we will favour intuitive notions over rigorous results.
The course will start with an introduction to the three fields and some probabilistic notions that will take the first four to five weeks. Then we will go into systems with negligible interactions such as the random energy models, shannon codes, or number partitioning. Then, if time allows it, models on graphs (low parity codes, SAT problems, spin glasses on graphs).

The course is based on parts I, II and III the book ”Information, Physics and Computation” by Marc Mezard and Andrea Montanari, see the table of contents and the chapters available at Montanaris’ webpage.

Date and time info
Wednesday 13:00 - 14:30

MSc students, PhD students, Postdocs


01.10.18 31.01.19

Regular lectures Winter semester 2018-2019

MPI for Mathematics in the Sciences / University of Leipzig see the lecture detail pages

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail