Information, Physics and Computation

  • Lecturer: Pau Vilimelis Aceituno
  • Date: Friday 13:00 - 14:30
  • Room: MPI MiS, A3 02
  • Language: English
  • Target audience: MSc students, PhD students, Postdocs


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, with the table of contents accessible here and the chapters available at Montanaris’ webpage

Regular Lectures (Winter 2018/2019)

15.10.2018, 08:45