Statistical Physics and Algorithms (Invited Talk)

The field of randomized algorithms has benefitted greatly from insights from statistical physics. We give examples in two distinct settings. The first is in the context of Markov chain Monte Carlo algorithms, which have become ubiquitous across science and engineering as a means of exploring large configuration spaces. One of the most striking discoveries was the realization that many natural Markov chains undergo phase transitions, whereby they are efficient for some parameter settings and then suddenly become inefficient as a parameter of the system is slowly modified. The second is in the context of distributed algorithms for programmable matter. Self-organizing particle systems based on statistical models with phase changes have been used to achieve basic tasks involving coordination, movement, and conformation in a fully distributed, local setting. We briefly describe these two settings to demonstrate how computing and statistical physics together provide powerful insights that apply across multiple domains