Finding and certifying a large hidden clique in a semirandom graph

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A" /><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

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

zbMATH Keywords

theta functionmaximum clique problemhidden cliquelargest cliquesemirandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (29)

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

• Geometric algorithms and combinatorial optimization.
• Matrix Analysis

This page was built for publication: Finding and certifying a large hidden clique in a semirandom graph