License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.50
URN: urn:nbn:de:0030-drops-119110
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11911/
Mohanty, Sidhanth ;
O'Donnell, Ryan ;
Paredes, Pedro
The SDP Value for Random Two-Eigenvalue CSPs
Abstract
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.
BibTeX - Entry
@InProceedings{mohanty_et_al:LIPIcs:2020:11911,
author = {Sidhanth Mohanty and Ryan O'Donnell and Pedro Paredes},
title = {{The SDP Value for Random Two-Eigenvalue CSPs}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {50:1--50:45},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11911},
URN = {urn:nbn:de:0030-drops-119110},
doi = {10.4230/LIPIcs.STACS.2020.50},
annote = {Keywords: Semidefinite programming, constraint satisfaction problems}
}
Keywords: |
|
Semidefinite programming, constraint satisfaction problems |
Collection: |
|
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
04.03.2020 |