Sum of squares lower bounds for refuting any CSP

DOI10.1145/3055399.3055485zbMath1370.68134arXiv1701.04521MaRDI QIDQ4977967

Ryan O'Donnell, Pravesh K. Kothari, Ryuhei Mori, David Witmer

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/1701.04521

zbMATH Keywords

lower bounds; constraint satisfaction; sum-of-squares semidefinite programming hierarchy

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C22: Semidefinite programming

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)