Abstract
We study the planted clique problem in which a clique of size k is planted in an ErdősRé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 statisticalcomputational gap at clique size k = Θ(√n), and has emerged as the prototypical problem with such a gap from which averagecase 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 statisticalcomputational phenomena to changes in our notion of computational efficiency, we ask
Do the statisticalcomputational 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 statisticalcomputational 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.
BibTeX  Entry
@InProceedings{mardia:LIPIcs.ITCS.2021.34,
author = {Jay Mardia},
title = {{Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {34:134:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13573},
URN = {urn:nbn:de:0030drops135734},
doi = {10.4230/LIPIcs.ITCS.2021.34},
annote = {Keywords: Statistical computational gaps, Planted clique, Space complexity, Average case computational complexity}
}
Keywords: 

Statistical computational gaps, Planted clique, Space complexity, Average case computational complexity 
Collection: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 
Issue Date: 

2021 
Date of publication: 

04.02.2021 