Statistical Algorithms and a Lower Bound for Detecting Planted Cliques

DOI10.1145/3046674zbMath1397.68085arXiv1201.1214OpenAlexW2607171573MaRDI QIDQ4640281

Y. Xiao, Elena Grigorescu, Lev Reyzin, Vitaly Feldman, Santosh Vempala

Publication date: 17 May 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

learning theorylower boundsplanted cliquestatistical algorithmsstatistical dimension

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Estimation of Wasserstein distances in the spiked transport model ⋮ Polynomial‐time universality and limitations of deep learning ⋮ Adversarial manifold estimation ⋮ Unnamed Item ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Unnamed Item ⋮ Finding a planted clique by adaptive probing ⋮ Exact recovery in the hypergraph stochastic block model: a spectral algorithm ⋮ The overlap gap property in principal submatrix recovery ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning