License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.1
URN: urn:nbn:de:0030-drops-118624
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11862/
Go to the corresponding LIPIcs Volume Portal

Randall, Dana

Statistical Physics and Algorithms (Invited Talk)

pdf-format:
LIPIcs-STACS-2020-1.pdf (0.3 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{randall:LIPIcs:2020:11862,
  author =	{Dana Randall},
  title =	{{Statistical Physics and Algorithms (Invited Talk)}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{1:1--1:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11862},
  URN =		{urn:nbn:de:0030-drops-118624},
  doi =		{10.4230/LIPIcs.STACS.2020.1},
  annote =	{Keywords: Markov chains, mixing times, phase transitions, programmable matter}
}

Keywords: Markov chains, mixing times, phase transitions, programmable matter
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI