The SDP value for random two-eigenvalue CSPs

DOI10.4230/LIPICS.STACS.2020.50arXiv1906.06732MaRDI QIDQ6320575FDOQ6320575

Authors: Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes

Publication date: 16 June 2019

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 $m a t h s f 2 X O R$ and $e x t s f N A E - 3 S A T$ , and includes new cases such as random $m a t h s f {S o r t}_{4}$ (equivalently, $m a t h s f C H S H$ ) and $m a t h s f F o r r e l a t i o n$ CSPs. Our techniques include new generalizations of the nonbacktracking operator, the Ihara--Bass Formula, and the Friedman/Bordenave proof of Alon's Conjecture.

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: The SDP value for random two-eigenvalue CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320575)