ARC Colloquium: Brice Huang (MIT)

Algorithms & Randomness Center (ARC)

Brice Huang (MIT)

December 5, 2022

Klaus 1116 - 11:00 am


Title: Algorithmic Thresholds for Multi-Species Spin Glasses

Abstract: This talk focuses on optimizing the random and non-convex Hamiltonians of spherical spin glasses with multiple species. Our main result identifies the best possible value ALG achievable by class of Lipschitz algorithms and gives a matching algorithm in this class based on approximate message passing. The threshold ALG is given by a certain variational problem, which surprisingly may possess multiple optimizers.

Our hardness result is proved using the Branching OGP introduced in our previous work [H-Sellke 21] to identify ALG for single-species spin glasses. This and all other OGPs for spin glasses have been proved using Guerra's interpolation method. We introduce a new method to prove the Branching OGP which is both simpler and more robust. It works even for models in which the true maximum value of the objective function remains unknown.
Based on joint work with Mark Sellke. 


Speaker's Webpage

Videos of recent talks are available at: and

Click here to subscribe to the seminar email list:

Event Details


  • Monday, December 5, 2022
    11:00 am - 12:00 pm