License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.34
URN: urn:nbn:de:0030-drops-135734
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13573/
Mardia, Jay
Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?
Abstract
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.
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:1--34:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13573},
URN = {urn:nbn:de:0030-drops-135734},
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 |
