Describing the fluctuations of the random assignment problem: Probability, statistical physics and AI experience

The random assignment problem asks for an optimal one-to-one matching between people and jobs when the assignment costs are independent random variables. A longstanding question concerns the fluctuations of the optimal total cost as the size of the problem grows. The problem has also served as a test bed for the replica method from statistical physics. In this talk, I will explain how recent advances in AI contributed to a proof of the conjectured Gaussian limit.