2026-07-25T14:48:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13573 2024-03-06T10:52:21Z ddc:004 open_access

Is the Space Complexity of Planted Clique Recovery the Same as That of Detection? Mardia, Jay Statistical computational gaps Planted clique Space complexity Average case computational complexity We study the planted clique problem in which a clique of size k is planted in an Erdős-Rényi graph G(n, 1/2), and one is interested in either detecting or recovering this planted clique. This problem is interesting because it is widely believed to show a statistical-computational gap at clique size k = Θ(√n), and has emerged as the prototypical problem with such a gap from which average-case hardness of other statistical problems can be deduced. It also displays a tight computational connection between the detection and recovery variants, unlike other problems of a similar nature. This wide investigation into the computational complexity of the planted clique problem has, however, mostly focused on its time complexity. To begin investigating the robustness of these statistical-computational phenomena to changes in our notion of computational efficiency, we ask- Do the statistical-computational phenomena that make the planted clique an interesting problem also hold when we use "space efficiency" as our notion of computational efficiency? It is relatively easy to show that a positive answer to this question depends on the existence of a O(log n) space algorithm that can recover planted cliques of size k = Ω(√n). Our main result comes very close to designing such an algorithm. We show that for k = Ω(√n), the recovery problem can be solved in O((log^*{n}-log^*{k/(√n}) ⋅ log n) bits of space. 1) If k = ω(√nlog^{(𝓁)}n) for any constant integer 𝓁 > 0, the space usage is O(log n) bits. 2) If k = Θ(√n), the space usage is O(log^* n ⋅ log n) bits. Our result suggests that there does exist an O(log n) space algorithm to recover cliques of size k = Ω(√n), since we come very close to achieving such parameters. This provides evidence that the statistical-computational phenomena that (conjecturally) hold for planted clique time complexity also (conjecturally) hold for space complexity. Due to space limitations, we omit proofs from this manuscript. The entire paper with full proofs can be found on arXiv at https://arxiv.org/abs/2008.12825. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jay Mardia 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.34 urn:nbn:de:0030-drops-135734 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.34 eng https://creativecommons.org/licenses/by/3.0/legalcode