10.4230/LIPICS.STACS.2020.1
Randall, Dana
Dana
Randall
School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332-0765, USA
Statistical Physics and Algorithms
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
ConferencePaper
Markov chains
mixing times
phase transitions
programmable matter
en
Christophe Paul
https://orcid.org/0000-0001-6519-975X
School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332-0765, USA
Markus Bläser
School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332-0765, USA
10.4230/LIPIcs.STACS.2020
978-3-95977-140-5
1868-8969
Creative Commons Attribution 3.0 Unported license
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.
LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 1:1-1:6