文章基本信息

标题：The SDP Value for Random Two-Eigenvalue CSPs
本地全文：下载
作者：Sidhanth Mohanty ; Ryan O'Donnell ; Pedro Paredes 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：50:1-50:45
DOI：10.4230/LIPIcs.STACS.2020.50
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Semidefinite programming; constraint satisfaction problems