A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

DOI10.1137/17M1138236zbMath1421.68056arXiv1604.03084OpenAlexW2943555824WikidataQ127965335 ScholiaQ127965335MaRDI QIDQ4634034

Boaz Barak, Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Ankur Moitra, Jonathan A. Kelner

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsum-of-squaresplanted clique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) 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

Isotonic regression with unknown permutations: statistics, computation and adaptation, Tensor clustering with planted structures: statistical optimality and computational limits, Disordered systems insights on computational hardness, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, Noisy tensor completion via the sum-of-squares hierarchy, Computational barriers to estimation from low-degree polynomials, Statistical limits of spiked tensor models, A faster interior-point method for sum-of-squares optimization, Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality, Free Energy Wells and Overlap Gap Property in Sparse PCA, Sum of Squares Bounds for the Empty Integral Hull Problem, Algorithmic obstructions in the random number partitioning problem, Compressive phase retrieval: Optimal sample complexity with deep generative priors, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, The Spectrum of the Grigoriev–Laurent Pseudomoments, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, Notes on computational-to-statistical gaps: predictions using statistical physics, A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares, The overlap gap property in principal submatrix recovery, On the computational tractability of statistical estimation on amenable graphs, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, The planted matching problem: phase transitions and exact results, Algorithmic thresholds for tensor PCA, Unnamed Item, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model, Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning, Optimal low-degree hardness of maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expected complexity of graph partitioning problems
• Hiding cliques for cryptographic security
• Public-key cryptography from different assumptions
• Sum-of-squares Lower Bounds for Planted Clique
• Sum of Squares Lower Bounds from Pairwise Independence
• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
• Hidden Cliques and the Certification of the Restricted Isometry Property
• How Hard Is It to Approximate the Best Nash Equilibrium?
• Random-Self-Reducibility of Complete Sets
• Information Theory and Statistical Mechanics
• Class of global minimum bounds of polynomial functions
• Large Cliques Elude the Metropolis Process
• On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
• Sum-of-squares proofs and the quest toward optimal algorithms
• Graph Matrices: Norm Bounds and Applications
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Harald Cramér and the distribution of prime numbers
• Rounding sum-of-squares relaxations
• Hypercontractivity, sum-of-squares proofs, and their applications
• On Worst‐Case to Average‐Case Reductions for NP Problems
• Complexity of Positivstellensatz proofs for the knapsack