Document Open Access Logo

Statistical Physics and Algorithms (Invited Talk)

Author Dana Randall

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.1.pdf
  • Filesize: 315 kB
  • 6 pages

Document Identifiers

Author Details

Dana Randall
  • School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332-0765, USA

Funding

Funded in part by NSF awards CCF-1526900, CCF-1637031, CCF-1733812 and ARO MURI award #W911NF-19-1-0233.

Cite As Get BibTex

Dana Randall. Statistical Physics and Algorithms (Invited Talk). In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 1:1-1:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.1

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Stochastic processes
  • Theory of computation → Self-organization
Keywords
  • Markov chains
  • mixing times
  • phase transitions
  • programmable matter

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A stochastic approach to shortcut bridging in programmable matter. In DNA Computing and Molecular Programming, DNA23, pages 122-138, 2017. Google Scholar
  2. Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A stochastic approach to shortcut bridging in programmable matter. Natural Computing, 17(4):723-741, 2018. Google Scholar
  3. Akhilest K. Arora and Raj Rajagopalan. Applications of colloids in studies of phase transitions and patterning of surfaces. Current Opinion in Colloid & Interface Science, 2(4), 1997. Google Scholar
  4. R. J. Baxter, I. G. Enting, and S. K. Tsang. Hard-square lattice gas. Journal of Statistical Physics, 22:465-489, 1980. Google Scholar
  5. Prateek Bhakta, Sarah Miracle, and Dana Randall. Clustering and mixing times for segregation models on ℤ². In Proceedings of the 25th ACM/SIAM Symposium on Discrete Algorithms, (SODA), 2014. Google Scholar
  6. Nayantara Bhatnagar and Dana Randall. Simulated tempering and swapping on mean-field models. Journal of Statistical Physics, 164(3):495-530, 2016. Google Scholar
  7. Antonio Blanca, Yuxuan Chen, David Galvin, Dana Randall, and Prasad Tetali. Phase coexistence for the hard-core model on ℤ². Combinatorics, Probability and Computing, pages 1-22, 2018. Google Scholar
  8. Antonio Blanca, David Galvin, Dana Randall, and Prasad Tetali. Coexistence and slow mixing for the hard-core model on ℤ². In Approximation, Randomization and Combinatorial Optimization (APPROX/RANDOM), volume 8096, pages 379-394, 2013. Google Scholar
  9. Bela Bollobas. The evolution of random graphs. Transactions of the American Mathematical Society, 286(1):257-274, 1984. Google Scholar
  10. Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, Alan Frieze, Prasad Tetali, Eric Vigoda, and Van Ha Vu. Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS '99, pages 218-229, Washington, DC, USA, 1999. IEEE Computer Society. Google Scholar
  11. Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. A local stochastic algorithm for separation in heterogeneous self-organizing particle systems. In Approximation, Randomization and Combinatorial Optimization (APPROX/RANDOM), pages 54:1-54:22, 2019. Google Scholar
  12. Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A Markov chain algorithm for compression in self-organizing particle systems. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 279-288, New York, NY, USA, 2016. ACM. Google Scholar
  13. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. An algorithmic framework for shape formation problems in self-organizing particle systems. In Proceedings of the Second Annual International Conference on Nanoscale Computing and Communication, NANOCOM '15, pages 21:1-21:2, 2015. Google Scholar
  14. Roland L. Dobrushin. The problem of uniqueness of a gibbsian random field and the problem of phase transitions. Functional Analysis and Its Applications, 2:302-312, 1968. Google Scholar
  15. Bahnisikha Dutta, Shengkai Li, Sarah Cannon, Joshua J. Daymude, Enes Aydin, Andrea W. Richa, Daniel I. Goldman, and Dana Randall. Programming robot collecitves using mechanics-induced phase changes, 2020. (In preparation). Google Scholar
  16. Sacha Friedli and Yvan Velenik. Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction. Cambridge University Press, Cambridge, 2017. Google Scholar
  17. Vivek K. Gore and Mark R. Jerrum. The Swendsen-Wang process does not always mix rapidly. Journal of Statistical Physics, 97(1):67-86, 1999. Google Scholar
  18. Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic pirogov-sinai theory. In Proceedings of the 51st Annual ACM Symposium on the Theory of Computing, pages 1009-1020, 2019. Google Scholar
  19. Svante Janson, Donald Knuth, Tomasz Luczak, and Boris Pittel. The birth of the giant component. Random Structures and Algorithms, 4(3):231-358, 1993. Google Scholar
  20. Mark R. Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Journal of the ACM, 51:671-697, 2004. Google Scholar
  21. Sarah Miracle, Dana Randall, and Amanda Pascoe Streib. Clustering in interfering binary mixtures. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX '11, RANDOM '11, pages 652-663, 2011. Google Scholar
  22. Gerald H. Pollack and Wei-Chun Chin (Eds.), editors. Phase Transitions in Cell Biology. Springer International Publishing, 2008. Google Scholar
  23. Chris R. Reid, Matthew J. Lutz, Scott Powell, Albert B. Kao, Iain D. Couzin, and Simon Garnier. Army ants dynamically adjust living bridges in response to a cost-benefit trade-off. Proceedings of the National Academy of Sciences, 112(49):15113-15118, 2015. Google Scholar
  24. William Savoie, Sarah Cannon, Joshua J. Daymude, Ross Warkentin, Shengkai Li, Andréa W. Richa, Dana Randall, and Daniel I. Goldman. Phototactic supersmarticles. Artificial Life and Robotics, 23(4):459-468, 2018. Google Scholar
  25. Thomas C. Schelling. Models of segregation. American Economic Review, 59(2):488-493, 1969. Google Scholar
  26. Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, and Yintong Yin. Spatial mixing and the connective constant: Optimal bounds. Probabability Theory Relatated Fields, 168(1-2):153-197, 2017. Google Scholar
  27. Leslie Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189-201, 1979. Google Scholar
  28. Jian-Sheng Wang and Robert H. Swendsen. Nonuniversal critical dynamics in monte carlo simulations. Physics Review Letters, 58(2):86-88, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact