Title

Critical Slowing Down in Polynomial Time Algorithms

Author(s)/Creator(s)

Alan Middleton, Syracuse UniversityFollow

Document Type

Article

Date

4-11-2011

Language

English

Disciplines

Physics

Description/Abstract

Combinatorial optimization algorithms which compute exact ground state configurations in disordered magnets are seen to exhibit critical slowing down at zero temperature phase transitions. Using arguments based on the physical picture of the model, including vanishing stiffness on scales beyond the correlation length and the ground state degeneracy, the number of operations carried out by one such algorithm, the push-relabel algorithm for the random field Ising model, can be estimated. Some scaling can also be predicted for the 2D spin glass.

Additional Information

4 pp., 3 figs More information at http://arxiv.org/abs/cond-mat/0104185

Recommended Citation

Middleton, Alan, "Critical Slowing Down in Polynomial Time Algorithms" (2011). Physics - All Scholarship. 193.
https://surface.syr.edu/phy/193

Source

Harvested from Arxiv.org

Creative Commons License

This work is licensed under a Creative Commons Attribution 3.0 License.