B9144 Statistical Physics, Markets and Algorithms
Fall 2019
Instructors: Yash Kanoria (Uris 404, ykanoria@columbia.edu)
TA: Yunbei Xu (Uris 4C, yunbei.xu@gsb.columbia.edu)
Syllabus
Statistical physics studies the macroscopic phenomena that emerge when a large number of simple units (like atoms or molecules) come together. Deep understanding developed in such study, especially the study of so-called “spin glasses” by Parisi, Mezard and others, has been leveraged to great effect in diverse areas including image processing, machine learning, computer science, and theoretical biology. This research-oriented PhD class will begin with the fundamentals of spin glasses. We will then proceed to the cavity method and message passing algorithms, including exciting recent developments in obtaining (1-\epsilon)-approximation algorithms for a range of problems satisfying “full replica symmetry breaking”. Lastly, we will cover some recent work by Peski on matching markets which has a distinct statistical physics flavor, with agents replacing atoms/molecules. More broadly, we will ask if statistical physics can tell us something about market equilibria, and perhaps about how to design better markets.
Session 1 (Fri, Sep 6th) Curie-Weiss Model, Random Energy Model Session Video Scribe Notes
Session 2 (Fri, Sep 13th) Constraint Satisfaction Problems Session Video Scribe Notes Random k-XORSAT slides
Session 3 (Mon, Sep 23rd) Factor Graphs, Message Passing Session Video Scribe Notes
Session 4 (Fri, Sep 27th) Message Passing, Variational Principles, Correlation Decay Session Video Scribe Notes
Session 5 (Fri, Oct 4th) Ruelle Probability Cascades and Ultrametricity Session Video Scribe Notes
Session 6 (Fri, 0ct 11th) Aizenmann-Sims-Starr Scheme and the Parisi Formula, Large Matching Markets Session Video Scribe Notes
Peski, Large roommate problem with non-transferable random utility, 2017.
Session 7 (Fri, Oct 25th) Threshold of Boolean Functions, TAP Free Energy and Variational Inference Session Video Scribe Notes
Fan et. al. TAP free energy, spin glasses, and variational inference, 2018.
Session 8 (Fri, Nov 1st) Generalized Random Energy Model, Naive Learning in Social Network Session Video Scribe Notes
Addario-Berry and Maillard, The algorithmic hardness threshold for continuous random energy models, 2018
Session 9 (Nov 8th) Local Algorithms Session Video Scribe Notes
Backhausz et. al. Correlation decay in local algorithms, 2013.
Gamarnik et. al. Correlation Decay in Random Decision Networks, 2013.
Session 10 (Fri, Nov. 15th) Parisi and Coppersmith-Sorkin formulae for random assignment, Approximate Message Passing Session Video
Wastlund, A simple proof of the Parisi and Coppersmith-Sorkin formulas for the random assignment problem, 2005.
Guest lecture: Prof. Cynthia Rush talking about approximate message passing: Slides
Session 11 (Fri, Nov. 22rd) Many-to-many search and matching, and a constructive proof of Parisi's formula Session Video Scribe Notes
Marcin Peski, Tractable Model of Dynamic Many-to-Many Matching, July 2019,
online Appendix with two extensions: a larger class of matchings (including multiple people and single events) and separation.
A. Montanari, Optimization of the Sherrington-Kirkpatrick Hamiltonian, 2019. Video
Session 12 (Fri, Dec 6th) Group Project Presentation