Sum of squares lower bounds for refuting any CSP

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

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

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 boundsconstraint satisfactionsum-of-squares semidefinite programming hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (26)

Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Towards breaking the exponential barrier for general secret sharing ⋮ Max-3-Lin over non-abelian groups with universal factor graphs ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Unnamed Item ⋮ Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ Unnamed Item ⋮ Indistinguishability obfuscation ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification ⋮ Sherali-adams strikes back ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Unnamed Item ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

This page was built for publication: Sum of squares lower bounds for refuting any CSP