Information, Physics and Computation

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).

References
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

Audience
MSc students, PhD students, Postdocs

Language
English