On the integrality gap of degree-4 sum of squares for planted clique
DOI10.1137/1.9781611974331.CH76zbMATH Open1410.05156OpenAlexW4244724628MaRDI QIDQ4575656FDOQ4575656
Tselil Schramm, Pravesh 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
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
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)
Cited In (9)
- The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
- Local and global expansion in random geometric graphs
- 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
- Title not available (Why is that?)
- 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
- Sum-of-squares Lower Bounds for Planted Clique
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)
