  We study the planted clique problem in which a clique of size k is planted in
an Erd\H{o}s-R\'enyi 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=sqrt{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. In this work, 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 = Omega(sqrt{n}). Our main result comes very close to designing such
an algorithm. We show that for k=Omega(sqrt{n}), the recovery problem can be
solved in O((log*{n}-log*{k/sqrt{n}}) log n) bits of space.
  1. If k = omega(sqrt{n}log^{(l)}n) for any constant integer l > 0, the space
usage is O(log n) bits.
  2.If k = Theta(sqrt{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 = Omega(sqrt{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.
