Finding and certifying a large hidden clique in a semirandom graph
From MaRDI portal
Publication:4948021
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.05050OpenAlexW2078758709WikidataQ56210408 ScholiaQ56210408MaRDI 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
Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Tensor clustering with planted structures: statistical optimality and computational limits, Independent sets in semi-random hypergraphs, On independent sets in random graphs, Unnamed Item, On combinatorial testing problems, Optimal detection of sparse principal components in high dimension, A simple spectral algorithm for recovering planted partitions, Finding one community in a sparse graph, Online Predictions for Online TSP on the Line, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, A Simple SVD Algorithm for Finding Hidden Partitions, Convex optimization for the planted \(k\)-disjoint-clique problem, Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation, Certifying algorithms, Finding large cliques in sparse semi-random graphs by simple randomized search heuristics, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Finding Hidden Cliques in Linear Time with High Probability, Recovering nonuniform planted partitions via iterated projection, Computational and statistical tradeoffs via convex relaxation, Nuclear norm minimization for the planted clique and biclique problems, 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, On the computational tractability of statistical estimation on amenable graphs, Nearly optimal robust secret sharing against rushing adversaries, Heuristics for semirandom graph 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
