Finding a planted clique by adaptive probing

MaRDI QIDQ5126325zbMATHFDO

Authors Miklós Z. Rácz, Benjamin Schiffer

Publication date 16 October 2020

Full work available at URL https://arxiv.org/abs/1903.12050

zbMATH Keywords

random graphplanted cliqueadaptive query model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial probability (60C05)

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 $GsimG(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(n^2/k^2+n)$ adaptive queries to the adjacency matrix of $G$ is likely to find the planted clique. On the other hand, when $kgeq(2+epsilon)lo{g}_{2}n$ there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making $q=O((n^2/k^2)lo{g}^{2}n+nlogn)$ 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 $n^2/k^2$ (up to logarithmic factors).

Recommendations

• Finding cliques using few probes
• Statistical algorithms and a lower bound for detecting planted cliques
• scientific article; zbMATH DE number 1303602
• scientific article; zbMATH DE number 1380608
• Statistical algorithms and a lower bound for detecting planted cliques

Cites work

• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• Cliques in random graphs
• Efficient noise-tolerant learning from statistical queries
• Expected complexity of graph partitioning problems
• Finding Hamilton cycles in random graphs with few queries
• Finding cliques using few probes
• Finding hidden cliques in linear time
• Finding hidden cliques in linear time with high probability
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Finding paths in sparse random graphs requires many queries
• Hiding cliques for cryptographic security
• Large Cliques Elude the Metropolis Process
• Online Ramsey numbers and the subgraph query problem
• Optimal detection of sparse principal components in high dimension
• Sparse CCA: adaptive estimation and computational barriers
• Statistical algorithms and a lower bound for detecting planted cliques

Cited in

(7)

• Statistical algorithms and a lower bound for detecting planted cliques
• Detecting a planted community in an inhomogeneous random graph
• Finding cliques using few probes
• Statistical algorithms and a lower bound for detecting planted cliques
• How to hide a clique?
• Algorithm for relatively small planted clique with small edge probability
• A new approach to the planted clique problem

This page was built for publication: Finding a planted clique by adaptive probing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5126325)