Critical slowing down in polynomial time algorithms

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.

4 pp., 3 figs

References in corpus (1)

• A fast Monte Carlo algorithm for site or bond percolation

Cited by in corpus (24)

• The three-dimensional random field Ising magnet: interfaces, scaling, and the nature of states
• Universality in the three-dimensional random-field Ising model
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Phase transitions in disordered systems: the example of the random-field Ising model in four dimensions
• Evidence for Supersymmetry in the Random-Field Ising Model at D = 5
• Restoration of dimensional reduction in the random-field Ising model at five dimensions
• Efficient numerical methods for the random-field Ising model: Finite-size scaling, reweighting extrapolation, and computation of response functions
• Critical exponents of four-dimensional random-field Ising systems
• Random Field Ising Model and Parisi-Sourlas Supersymmetry. Part II. Renormalization Group
• Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
• No-passing Rule in the Ground State Evolution of the Random-Field Ising Model
• Negative-weight percolation
• Finite-size scaling of the random-field Ising model above the upper critical dimension
• First excitations in two- and three-dimensional random-field Ising systems
• Specific-heat exponent and modified hyperscaling in the 4D random-field Ising model
• Random-field Ising model: Insight from zero-temperature simulations
• Low-energy excitations in the three-dimensional random-field Ising model
• The dynamics of a driven harmonic oscillator coupled to independent Ising spins in random fields
• On the critical exponent $\alpha$ of the 5D random-field Ising model
• Analysis of the loop length distribution for the negative weight percolation problem in dimensions d=2 through 6
• Excitations in high-dimensional random-field Ising magnets
• Effect of disorder on condensation in the lattice gas model on a random graph
• Work distributions in the T=0 Random Field Ising Model
• Efficient algorithms for computing ground states of the 2D random-field Ising model