Analyzing dynamics and average case complexity in the spherical Sherrington-Kirkpatrick model: a focus on extreme eigenvectors

2024/01/08 by Yu, Tingzhou
#FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Numerical Analysis (math.NA) #Probability (math.PR)

paper · doi:10.48550/arxiv.2401.03668

Abstract

We explore Langevin dynamics in the spherical Sherrington-Kirkpatrick model, delving into the asymptotic energy limit. Our approach involves integro-differential equations, incorporating the Crisanti-Horner-Sommers-Cugliandolo-Kurchan equation from spin glass literature, to analyze the system's size and its temperature-dependent phase transition. Additionally, we conduct an average case complexity analysis, establishing hitting time bounds for the bottom eigenvector of a Wigner matrix. Our investigation also includes the power iteration algorithm, examining its average case complexity in identifying the top eigenvector overlap, with comprehensive complexity bounds.

Related

• Evidence for a Vanishing Complexity of the Sherrington-Kirkpatrick model
• The Threshold Energy of Low Temperature Langevin Dynamics for Pure Spherical Spin Glasses
• Some aspects of infinite range models of spin glasses: theory and numerical simulations
• Spherical Sherrington-Kirkpatrick model for deformed Wigner matrix with fast decaying edges
• High temperature Sherrington-Kirkpatrick model for general spins