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.