2026-07-23T07:58:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17580 2024-03-06T10:59:58Z ddc:004 open_access

Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses Jones, Chris Marwaha, Kunal Sandhu, Juspreet Singh Shi, Jonathan spin glass overlap gap property constraint satisfaction problem Guerra-Toninelli interpolation 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chris Jones and Kunal Marwaha and Juspreet Singh Sandhu and Jonathan Shi 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.77 urn:nbn:de:0030-drops-175804 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.77 eng https://creativecommons.org/licenses/by/4.0/legalcode