Strongly refuting random CSPs below the spectral threshold

DOI10.1145/3055399.3055417zbMath1370.68140arXiv1605.00058OpenAlexW2345432430MaRDI QIDQ4977966

No author found.

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.00058

zbMATH Keywords

random constraint satisfaction problemsspectral algorithmssum-of-squares hierarchystrong refutation

Mathematics Subject Classification ID

Related Items (9)

Disordered systems insights on computational hardness ⋮ Noisy tensor completion via the sum-of-squares hierarchy ⋮ Towards breaking the exponential barrier for general secret sharing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sherali-adams strikes back ⋮ Unnamed Item ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

This page was built for publication: Strongly refuting random CSPs below the spectral threshold