Critical Slowing Down in Polynomial Time Algorithms

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

Combinatorial optimization algorithms that compute exact ground states for disordered magnets are seen to exhibit critical slowing down at zero temperature phase transitions. Using the physical features of the models, such as vanishing stiffness on one side of the transition and the ground state degeneracy, the number of operations needed in the push-relabel algorithm for the random field Ising model and in the algorithm for the 2D spin glass is estimated. These results strengthen the connections between algorithms and the physical picture and may be used to improve the speed of computations.

Original languageEnglish (US)
Pages (from-to)4
Number of pages1
JournalPhysical Review Letters
Volume88
Issue number1
DOIs
StatePublished - 2002

ASJC Scopus subject areas

  • Physics and Astronomy(all)

Fingerprint Dive into the research topics of 'Critical Slowing Down in Polynomial Time Algorithms'. Together they form a unique fingerprint.

  • Cite this