TY - GEN
T1 - The SDP value for random two-eigenvalue CSPs
AU - Mohanty, Sidhanth
AU - O'Donnell, Ryan
AU - Paredes, Pedro
N1 - Funding Information:
Funding Sidhanth Mohanty: Supported by NSF grant CCF-1718695. Ryan O’Donnell: Supported by NSF grant CCF-1717606. This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF). Pedro Paredes: Supported by NSF grant CCF-1717606.
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 -