Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time

DOI10.1007/s10208-014-9215-yzbMath1347.05227arXiv1304.7047OpenAlexW2962704928MaRDI QIDQ896557

Yash Deshpande, Andrea Montanari

Publication date: 10 December 2015

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graphsaverage case complexitysparse recoverylocal algorithmsbelief propagationapproximate message passing

Mathematics Subject Classification ID

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

Related Items

Tensor clustering with planted structures: statistical optimality and computational limits, Computational barriers to estimation from low-degree polynomials, Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times, High dimensional robust M-estimation: asymptotic variance via approximate message passing, Estimation of low-rank matrices via approximate message passing, Fundamental limits of weak recovery with applications to phase retrieval, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, A Simple SVD Algorithm for Finding Hidden Partitions, Notes on computational-to-statistical gaps: predictions using statistical physics, Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications, Parallel tempering for the planted clique problem, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Submatrix localization via message passing, The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time, Finding a planted clique by adaptive probing, Convex optimization for the densest subgraph and densest submatrix problems, Universality of approximate message passing algorithms, On the computational tractability of statistical estimation on amenable graphs, Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs, The committee machine: computational to statistical gaps in learning a two-layers neural network, Consistency of spectral clustering in stochastic block models, Sparsistency and agnostic inference in sparse PCA, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, A Unifying Tutorial on Approximate Message Passing, 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, Robust and computationally feasible community detection in the presence of arbitrary outlier nodes, Computational barriers in minimax submatrix detection, Do semidefinite relaxations solve sparse PCA up to the information limit?

Uses Software

• LAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal detection of sparse principal components in high dimension
• On combinatorial testing problems
• Nuclear norm minimization for the planted clique and biclique problems
• Finding large average submatrices in high dimensional data
• The eigenvalues of random symmetric matrices
• On the concentration of eigenvalues of random symmetric matrices
• Universality in polytope phase transitions and message passing algorithms
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Detection of an anomalous cluster in a network
• The Isotropic Semicircle Law and Deformation of Wigner Matrices
• Survey of local algorithms
• Robust principal component analysis?
• Modern Coding Theory
• Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods
• Graphical Models, Exponential Families, and Variational Inference
• Information, Physics, and Computation
• Locality in Distributed Graph Algorithms
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• What Can be Computed Locally?
• Iterative reconstruction of rank-one matrices in noise
• Rejoinder
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Finding Hidden Cliques in Linear Time with High Probability
• Statistical algorithms and a lower bound for detecting planted cliques
• The Rotation of Eigenvectors by a Perturbation. III
• A Direct Formulation for Sparse PCA Using Semidefinite Programming