TY - GEN
T1 - The SDP value for random two-eigenvalue CSPs
AU - Mohanty, Sidhanth
AU - O'Donnell, Ryan
AU - Paredes, Pedro
N1 - Publisher Copyright:
© Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes; licensed under Creative Commons License CC-BY
PY - 2020/3
Y1 - 2020/3
N2 - 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 Sort4 (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.
AB - 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 Sort4 (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.
KW - Constraint satisfaction problems
KW - Semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=85082139092&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85082139092&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2020.50
DO - 10.4230/LIPIcs.STACS.2020.50
M3 - Conference contribution
AN - SCOPUS:85082139092
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
A2 - Paul, Christophe
A2 - Blaser, Markus
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
Y2 - 10 March 2020 through 13 March 2020
ER -