  The planted clique problem is well-studied in the context of observing,
explaining, and predicting interesting computational phenomena associated with
statistical problems. When equating computational efficiency with the existence
of polynomial time algorithms, the computational hardness of (some variant of)
the planted clique problem can be used to infer the computational hardness of a
host of other statistical problems.
  Is this ability to transfer computational hardness from (some variant of) the
planted clique problem to other statistical problems robust to changing our
notion of computational efficiency to space efficiency?
  We answer this question affirmatively for three different statistical
problems, namely Sparse PCA, submatrix detection, and testing almost k-wise
independence. The key challenge is that space efficient randomized reductions
need to repeatedly access the randomness they use. Known reductions to these
problems are all randomized and need polynomially many random bits to
implement. Since we can not store polynomially many random bits in memory, it
is unclear how to implement these existing reductions space efficiently. There
are two ideas involved in circumventing this issue and implementing known
reductions to these problems space efficiently.
  1. When solving statistical problems, we can use parts of the input itself as
randomness.
  2. Secret leakage variants of the planted clique problem with appropriate
secret leakage can be more useful than the standard planted clique problem when
we want to use parts of the input as randomness.
  (abstract shortened due to arxiv constraints)
