Finding hidden cliques in linear time

MaRDI QIDQ2959905zbMATH OpenFDO

Authors Dorit Ron, Uriel Feige

Publication date 10 February 2017

Full work available at URL http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0114

zbMATH Keywords

hidden cliquerandom graphs

Mathematics Subject Classification ID

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

Recommendations

• Finding hidden cliques in linear time with high probability
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Finding hidden cliques in linear time with high probability
• scientific article; zbMATH DE number 1380608
• scientific article; zbMATH DE number 1303602

Cited in

(32)

• Convex optimization for the densest subgraph and densest submatrix problems
• A simple spectral algorithm for recovering planted partitions
• Tensor clustering with planted structures: statistical optimality and computational limits
• On the hardness of designing public signals
• Computational barriers in minimax submatrix detection
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Community detection in dense random networks
• Optimal detection of sparse principal components in high dimension
• scientific article; zbMATH DE number 1303602 (Why is no real title available?)
• A Simple SVD Algorithm for Finding Hidden Partitions
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• Finding and certifying a large hidden clique in a semirandom graph
• Finding a planted clique by adaptive probing
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Finding hidden cliques in linear time with high probability
• Superlogarithmic cliques in dense inhomogeneous random graphs
• Finding hidden cliques in linear time with high probability
• Algorithms – ESA 2005
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Cryptography from planted graphs: security with logarithmic-size messages
• How to hide a clique?
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• How to hide a clique?
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• Almost-linear planted cliques elude the Metropolis process
• Tensor factor model estimation by iterative projection
• Analysis of singular subspaces under random perturbations
• Is the space complexity of planted clique recovery the same as that of detection?
• 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

This page was built for publication: Finding hidden cliques in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959905)