Finding Hidden Cliques in Linear Time with High Probability

DOI10.1017/S096354831300045XzbMath1290.05129arXiv1010.2997WikidataQ57568011 ScholiaQ57568011MaRDI QIDQ5414144

Yael Dekel, Ori Gurel-Gurevich, Yuval Peres

Publication date: 2 May 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

linear time algorithmrandom graphhidden clique

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Tensor clustering with planted structures: statistical optimality and computational limits, Energy landscape for large average submatrix detection problems in Gaussian random matrices, Optimal detection of sparse principal components in high dimension, A simple spectral algorithm for recovering planted partitions, Finding one community in a sparse graph, Community detection in sparse random networks, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, A Simple SVD Algorithm for Finding Hidden Partitions, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time, Cliques in rank-1 random graphs: the role of inhomogeneity, Community detection in dense random networks, Finding a planted clique by adaptive probing, Convex optimization for the densest subgraph and densest submatrix problems, Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning, Computational barriers in minimax submatrix detection, Do semidefinite relaxations solve sparse PCA up to the information limit?

Cites Work

• Unnamed Item
• Unnamed Item
• Expected complexity of graph partitioning problems
• Hiding cliques for cryptographic security
• Weighted sums of certain dependent random variables
• Probabilistic checking of proofs
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Finding and certifying a large hidden clique in a semirandom graph
• Probability