Create
Design Project Gallery
Reluctant dynamics for binary optimization and spin glass
- Program: Applied Mathematics and Statistics
- Course: Other
- Year: 2025
Project Description:
Spin glasses are disordered systems in statistical physics with randomly interacting particles; the Sherrington-Kirkpatrick (SK) model is a widely studied idealization that represents such systems using ±1-valued “spins” and random couplings. These random interactions create “frustration,” a phenomenon where conflicting constraints prevent spins from all aligning optimally. This results in a complex energy landscape with many local minima, making global optimization both computationally challenging and theoretically rich. A central focus of this project is the study of universality: whether algorithmic behaviors are determined solely by broad statistical features of the system or if they depend on finer distributional details. By analyzing algorithms that interpolate between greedy and reluctant local updates, we examine the geometry and complexity of optimizing the SK model. Since many NP-hard problems, such as Max-Cut and Vertex Cover, can be reformulated as spin glass systems, understanding these dynamics offers broader insights into designing effective heuristics for complex optimization problems.
Project Photo:
An energy landscape illustrating the complex structure of local minima in spin glass models.