2026-07-26T23:09:40Z https://drops.dagstuhl.de/oai

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

The SDP Value for Random Two-Eigenvalue CSPs Mohanty, Sidhanth O'Donnell, Ryan Paredes, Pedro Semidefinite programming constraint satisfaction problems We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, "two-eigenvalue 2CSPs". We show this SDP value coincides with the spectral relaxation value, possibly indicating a computational threshold. Our analysis extends the previously resolved cases of random regular 2XOR and NAE-3SAT, and includes new cases such as random Sort₄ (equivalently, CHSH) and Forrelation CSPs. Our techniques include new generalizations of the nonbacktracking operator, the Ihara-Bass Formula, and the Friedman/Bordenave proof of Alon’s Conjecture. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sidhanth Mohanty and Ryan O'Donnell and Pedro Paredes 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.50 urn:nbn:de:0030-drops-119110 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.50 eng https://creativecommons.org/licenses/by/3.0/legalcode