Finding Hidden Cliques in Linear Time with High Probability

DOI10.1137/1.9781611973013.8zbMath1430.68470OpenAlexW4230257222MaRDI QIDQ5194692

Ori Gurel-Gurevich, Yael Dekel, Yuval Peres

Publication date: 16 September 2019

Published in: 2011 Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973013.8

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Random perturbation of low rank matrices: improving classical bounds ⋮ On the hardness of designing public signals ⋮ Recovering the structure of random linear graphs

This page was built for publication: Finding Hidden Cliques in Linear Time with High Probability