The k-planted clique detection conjecture

Fix a constant p(0,1)p\in(0,1). Let EE be a fixed known partition of [n][n] into knk_n equally sized subsets, and under the alternative choose exactly one planted clique vertex uniformly from each part. Let k\textscPCD(n,kn,p)k\textsc{-PC}_D(n,k_n,p) denote the resulting detection problem, with hypotheses H0H_0 and H1H_1. For randomized polynomial-time algorithms An:Gn{0,1}A_n:G_n\to\{0,1\} and positive-integer sequences knk_n satisfying

lim supnlognkn<12,\limsup_{n\to\infty}\log_n k_n<\frac{1}{2},

the kk-planted clique conjecture. If GG is an instance of k\textscPCD(n,kn,p)k\textsc{-PC}_D(n,k_n,p), then

lim infn(PH0[An(G)=1]+PH1[An(G)=0])1.\liminf_{n\to\infty}\left(\mathbb{P}_{H_0}[A_n(G)=1]+\mathbb{P}_{H_1}[A_n(G)=0]\right)\geq 1.

This is a planted-clique hardness assumption with secret leakage: the algorithm knows the partition, while the planted set contains one uniformly selected vertex from each part. The supplied text gives no evidence that the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Guy Bresler and Tianze Jiang, “Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique”, arXiv:2306.17719 (2023).

Additional references

3 papers in this index state this conjecture (2019–2023). The statement above is taken from the most recent of them; the others are arXiv:1902.07380, arXiv:1902.06916.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.