On the integrality gap of degree-4 sum of squares for planted clique

DOI10.1137/1.9781611974331.CH76MaRDI QIDQ4575656zbMATHOpenAlexFDO

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

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

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

Recommendations

• On the integrality gap of degree-4 sum of squares for planted clique
• Sum-of-squares Lower Bounds for Planted Clique
• A nearly tight sum-of-squares lower bound for the planted clique problem
• A new approach to the planted clique problem
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian

Cited in

(11)

• Sum-of-squares Lower Bounds for Planted Clique
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Random Tensors and Planted Cliques
• Average-case complexity of tensor decomposition for low-degree polynomials
• Algorithms approaching the threshold for semi-random planted clique
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Local and global expansion in random geometric graphs
• On the integrality gap of degree-4 sum of squares for planted clique
• The Lovász theta function for random regular graphs and community detection in the hard regime
• A nearly tight sum-of-squares lower bound for the planted clique problem
• Sherali-Adams integrality gaps matching the log-density threshold

This page was built for publication: On the integrality gap of degree-4 sum of squares for planted clique

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