CS 8803: Statistical Physics in Algorithms and Combinatorics

CS 8803

Spring 2025

Monday, Wednesday 12:30 - 1:45 pm in Molecular Sciences 1224

Instructor

Will Perkins

[email protected]

Office: Klaus 2222

Office Hours: Wednesdays 11:30-12:30pm, or by appointment

Course Information

Main Topics of the Course:

  1. Fundamentals of statistical physics: Gibbs measures, partition functions, correlations, cumulants
  2. Models: Ising, Potts, hard-core, spin glasses, perceptron
  3. Phase transitions, uniquenes of Gibbs measure, Lee-Yang theory
  4. Cluster expansion
  5. Phase coexistence: Peierls' arguments, Pirogov-Sinai theory
  6. Thresholds in random graphs
  7. Random CSP's
  8. Large deviations in random graphs
  9. Statistical inference and planted models
  10. Cavity method
  11. Solution space geometry and algorithmic barriers
References
Schedule
  • Jan 6What is statistical physics?

  • Jan 8Gibbs measures, maximum entropy, partition functions, boundary conditions

    Homework 1

  • Jan 13Three definitions of phase transition

  • Jan 15Two theorems in extremal combinatorics with one proof

  • Jan 20NO CLASS - MLK Day

  • Jan 22Gibbs measures on trees and random graphs

    Homework 2

  • Jan 27Belief propagation, moment method

  • Jan 29

  • Feb 3

  • Feb 5

  • Feb 10

  • Feb 12

  • Feb 17

  • Feb 19

  • Feb 24

  • Feb 26

  • Mar 3

  • Mar 5

  • Mar 10

  • Mar 12

  • Mar 24

  • Mar 26

  • Mar 31

  • Apr 2

  • Apr 7

  • Apr 9

  • Apr 14

  • Apr 16

  • Apr 21