Finding a planted clique by adaptive probing

Miklós Z. Rácz, Benjamin Schiffer

Research output: Contribution to journalArticlepeer-review

Abstract

We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let G ~ G(n, 1/2, k) be a random graph on n vertices with a planted clique of size k. We show that no algorithm that makes at most q = o(n2/k2 + n) adaptive queries to the adjacency matrix of G is likely to find the planted clique. On the other hand, when k ≥ (2 + ε) log2 n there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making q = O(n2/k2) log2 n + n log n) adaptive queries. For detection, the additive n term is not necessary: the number of queries needed to detect the presence of a planted clique is n2/k2 (up to logarithmic factors).

Original languageEnglish (US)
Pages (from-to)759-773
Number of pages15
JournalAlea
Volume17
Issue number2
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Statistics and Probability

Keywords

  • Adaptive query model
  • Planted clique
  • Random graph

Fingerprint

Dive into the research topics of 'Finding a planted clique by adaptive probing'. Together they form a unique fingerprint.

Cite this