The SDP value for random two-eigenvalue CSPs

Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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.

Original languageAmerican English
Title of host publication37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
EditorsChristophe Paul, Markus Blaser
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771405
DOIs
StatePublished - Mar 2020
Externally publishedYes
Event37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020 - Montpellier, France
Duration: Mar 10 2020Mar 13 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume154

Conference

Conference37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
Country/TerritoryFrance
CityMontpellier
Period3/10/203/13/20

ASJC Scopus subject areas

  • Software

Keywords

  • Constraint satisfaction problems
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'The SDP value for random two-eigenvalue CSPs'. Together they form a unique fingerprint.

Cite this