Sum-of-squares Lower Bounds for Planted Clique

DOI10.1145/2746539.2746600zbMath1321.05241arXiv1503.06447OpenAlexW2033515640WikidataQ56210431 ScholiaQ56210431MaRDI QIDQ2941492

Avi Wigderson, Raghu Meka, Aaron Potechin

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.06447

Mathematics Subject Classification ID

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

Related Items (21)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time ⋮ The overlap gap property in principal submatrix recovery ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

Uses Software

• Graphs

Cites Work

• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Unnamed Item

This page was built for publication: Sum-of-squares Lower Bounds for Planted Clique