We study random constraint satisfaction problems (CSPs) in the unsatisfiable
regime. We relate the structure of near-optimal solutions for any Max-CSP to
that for an associated spin glass on the hypercube, using the Guerra-Toninelli
interpolation from statistical physics. The noise stability polynomial of the
CSP’s predicate is, up to a constant, the mixture polynomial of the associated
spin glass. We prove two main consequences:
1) We relate the maximum fraction of constraints that can be satisfied in a
random Max-CSP to the ground state energy density of the corresponding spin
glass. Since the latter value can be computed with the Parisi formula, we
provide numerical values for some popular CSPs.
2) We prove that a Max-CSP possesses generalized versions of the overlap gap
property if and only if the same holds for the corresponding spin glass. We
transfer results from Huang et al. [arXiv:2110.07847, 2021] to obstruct
algorithms with overlap concentration on a large class of Max-CSPs. This
immediately includes local classical and local quantum algorithms.
