On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

DOI10.1137/1.9781611974331.ch76zbMath1410.05156OpenAlexW4244724628MaRDI QIDQ4575656

Tselil Schramm, Pravesh K. Kothari, Samuel B. Hopkins, Aaron Potechin, Prasad Raghavendra

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch76

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Unnamed Item ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

This page was built for publication: On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique