Let ${boldsymbol A}in{mathbb R}^{ntimes n}$ be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing $langle{boldsymbol sigma},{boldsymbol A}{boldsymbol sigma}rangle$ over binary vectors ${boldsymbol sigma}in{+1,-1}^n$. In the language of statistical physics, this amounts to finding the ground state of the Sherrington-Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any $varepsilon>0$, outputs ${boldsymbol sigma}_*in{-1,+1}^n$ such that $langle{boldsymbol sigma}_*,{boldsymbol A}{boldsymbol sigma}_*rangle$ is at least $(1-varepsilon)$ of the optimum value, with probability converging to one as $ntoinfty$. The algorithms time complexity is $C(varepsilon), n^2$. It is a message-passing algorithm, but the specific structure of its update rules is new. As a side result, we prove that, at (low) non-zero temperature, the algorithm constructs approximate solutions of the Thouless-Anderson-Palmer equations.
Download