{"id":"arxiv/2609.24780","url":"https://arxiv.org/abs/2609.24780","tags":["cs.DS","math.ST"],"score":0,"title":"Improved polynomial-time algorithms for detecting and recovering planted $Θ(\\sqrt{n})$-cliques","domain":"cs.DS","source":"arxiv","authors":["Dmitriy Kunisky","Songtao Mao"],"reviews":0,"subject":"cs.DS","summary":"In the planted clique problem, one observes either an Erdős--Rényi graph on $n$ vertices or such a graph with a clique added to $k = k(n)$ vertices, and seeks to detect or recover the clique. It is widely believed that $k = Θ(\\sqrt{n})$ is the smallest clique size for which polynomial-time algorithms exist for these tasks. We develop new algorithms in this regime using color-coding to estimate signed subgraph counts, further accelerated with fast matrix multiplication. We first show that, for each $t \\geq 1$, for $c(t)$ a constant associated to the order of growth of the number of connected…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-21","reactions":{}}