1 Search Results for "Mardia, Jay"

Document

DOI: 10.4230/LIPIcs.ITCS.2021.34

Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?

Authors: Jay Mardia

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

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.

Cite as

Jay Mardia. Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mardia:LIPIcs.ITCS.2021.34,
  author =	{Mardia, Jay},
  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 =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.34},
  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}
}

Refine by Author
1 Mardia, Jay

Refine by Classification
1 Theory of computation → Computational complexity and cryptography

Refine by Keyword
1 Average case computational complexity
1 Planted clique
1 Space complexity
1 Statistical computational gaps

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Mardia, Jay"

Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?

Abstract

Cite as

Thanks for your feedback!

Could not send message