CAREER: Algorithmic Spin Glass Theory: Computational and Landscape Phase Transitions

Modern science and technology increasingly relies on algorithms that must search through enormous spaces of possibilities: training an artificial intelligence model, discovering patterns in data, or producing many independent samples from a complex probability distribution. In many such problems, the underlying landscape is high-dimensional and filled with many competing basins of attraction. This project develops mathematics to explain when such landscapes can be navigated efficiently, and when they contain intrinsic barriers that no broad class of algorithms can overcome. The central models of study originate in spin glass theory, which began in statistical physics to study disordered materials and is now deeply connected to probability, optimization, machine learning, and theoretical computer science. The project will clarify the fundamental limits of algorithms for random optimization and sampling, with implications for diffusion-based generative AI, combinatorial optimization, random matrix theory, and quantum algorithms. The educational component of the project will train students and early-career researchers through mentoring, new course materials, and a summer school on spin glasses and algorithms. Technically, the project develops algorithmic spin glass theory as a framework for computational and landscape phase transitions. It will study optimization and sampling thresholds in mean-field spin glasses, random constraint satisfaction problems, discrepancy and perceptron models, and other related models. A central tool is the branching overlap gap property, which identifies geometric obstructions to stable algorithms and gives sharp thresholds for broad algorithmic classes. The project will connect these obstructions with low-degree polynomial methods as evidence for fine-grained computational hardness, and will use the resulting theory to benchmark recently proposed quantum algorithms for constraint satisfaction problems. It will also study algorithms and barriers to sampling from spin glass Gibbs measures through diffusion methods, motivated in part by their connection to modern generative AI. A second direction will prove universality results for dynamical and landscape phenomena, develop the first rigorous certifiable methods to compute replica-symmetry-breaking structure in mean-field spin glasses, and apply techniques from spin glass theory to problems in random matrix theory. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.