Finding and certifying a large hidden clique in a semirandom graph
From MaRDI portal
DOI<195::AID-RSA5>3.0.CO;2-A 10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-AzbMath0940.05050MaRDI QIDQ4948021
Robert Krauthgamer, Uriel Feige
Publication date: 13 July 2000
Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(200003)16:2<195::aid-rsa5>3.0.co;2-a
05C80: Random graphs (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
A Simple SVD Algorithm for Finding Hidden Partitions, Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation, Unnamed Item, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Computational and statistical tradeoffs via convex relaxation, Finding Hidden Cliques in Linear Time with High Probability, Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning, Optimal detection of sparse principal components in high dimension, Certifying algorithms, On combinatorial testing problems, Nuclear norm minimization for the planted clique and biclique problems, Independent sets in semi-random hypergraphs, Finding one community in a sparse graph, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Heuristics for semirandom graph problems, A simple spectral algorithm for recovering planted partitions, Recovering nonuniform planted partitions via iterated projection, On the computational tractability of statistical estimation on amenable graphs, Nearly optimal robust secret sharing against rushing adversaries, Tensor clustering with planted structures: statistical optimality and computational limits, Cliques in rank-1 random graphs: the role of inhomogeneity, On the hardness of designing public signals, Exact recovery in the hypergraph stochastic block model: a spectral algorithm, Computational barriers in minimax submatrix detection, Do semidefinite relaxations solve sparse PCA up to the information limit?, Convex optimization for the planted \(k\)-disjoint-clique problem, Finding large cliques in sparse semi-random graphs by simple randomized search heuristics, On independent sets in random graphs
Cites Work
