- Title题目 Fragile yet Local: A New View of Spin Glasses and the Algorithms It Inspires
- Speaker报告人 沈牧天/Mu-Tian Shen (General Motors Company)
- Date日期 2026年11月25日 10:30
- Venue地点 Zoom: 81673970676, Passcode: 422194, https://us06web.zoom.us/j/81673970676?pwd=y7ab9NTMKaebForxHnCu6mjowHMure.1
Spin glasses are disordered systems with a seemingly simple Hamiltonian but an extraordinarily complex energy landscape. Finding their ground states is central to understanding their low-temperature physics and is closely tied to a broad class of NP-hard optimization problems. At first sight, divide-and-conquer strategies seem doomed here: large, low-energy excitations emerge across the boundaries between subsystems, so local optima cannot simply be stitched into a global one. Must we then abandon local computation altogether? We argue that we need not. We introduce a new measure of computational complexity, local hardness: how large a subsystem a local solver needs to reach a given accuracy. We find that finite-dimensional lattice spin glasses sit at a level of local hardness where local solvers are effective. The local error decays as a power law in subsystem size and does not depend on the total system size, whether the problem is in P (2D) or NP-hard (3D). Moreover, the stability of each bond, defined as the distance between its coupling and its critical threshold, can be computed from local information alone and predicts how accurate the local solver will be on that bond. This leads us to a contraction solver: it fixes the stable, “easy” variables, contracts them into effective spins, and leaves only the few “hard” ones, which greatly reduces the size of the problem to be solved.
Biography
Dr. Mutian Shen is an AI Researcher at General Motors Company.
Inviter: Hai-Jun Zhou