License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.77
URN: urn:nbn:de:0030-drops-175804
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17580/
Jones, Chris ;
Marwaha, Kunal ;
Sandhu, Juspreet Singh ;
Shi, Jonathan
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
Abstract
We study random constraint satisfaction problems (CSPs) at large clause density. We relate the structure of near-optimal solutions for any Boolean 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 show two main consequences:
1) We prove that the maximum fraction of constraints that can be satisfied in a random Max-CSP at large clause density is determined by the ground state energy density of the corresponding spin glass. Since the latter value can be computed with the Parisi formula [Parisi, 1980; Talagrand, 2006; Auffinger and Chen, 2017], we provide numerical values for some popular CSPs.
2) We prove that a Max-CSP at large clause density 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 and Sellke, 2021] to obstruct algorithms with overlap concentration on a large class of Max-CSPs. This immediately includes local classical and local quantum algorithms [Chou et al., 2022].
BibTeX - Entry
@InProceedings{jones_et_al:LIPIcs.ITCS.2023.77,
author = {Jones, Chris and Marwaha, Kunal and Sandhu, Juspreet Singh and Shi, Jonathan},
title = {{Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {77:1--77:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17580},
URN = {urn:nbn:de:0030-drops-175804},
doi = {10.4230/LIPIcs.ITCS.2023.77},
annote = {Keywords: spin glass, overlap gap property, constraint satisfaction problem, Guerra-Toninelli interpolation}
}
