# Logspace Reducibility From Secret Leakage Planted Clique

arXiv: https://arxiv.org/abs/2107.11886 · HTML: https://mlsanity.com/paper/2107.11886/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 83 references that are in the map.
- First posted on arXiv 25 Jul 2021.

## Builds on (most cited first, 25 of 25)

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [Universality of Computational Lower Bounds for Submatrix Detection](https://mlsanity.com/paper/1902.06916/) (2019)
- [Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness](https://mlsanity.com/paper/1902.07380/) (2019)
- [Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix](https://mlsanity.com/paper/1502.01988/) (2015)
- [Sum-of-squares lower bounds for planted clique](https://mlsanity.com/paper/1503.06447/) (2015)
- [Counterexamples to the Low-Degree Conjecture](https://mlsanity.com/paper/2004.08454/) (2020)
- [Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems](https://mlsanity.com/paper/1502.06590/) (2015)
- [The Strongish Planted Clique Hypothesis and Its Consequences](https://mlsanity.com/paper/2011.05555/) (2020)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Robust Sparse Estimation Tasks in High Dimensions](https://mlsanity.com/paper/1702.05860/) (2017)
- [Finding Planted Cliques in Sublinear Time](https://mlsanity.com/paper/2004.12002/) (2020)
- [The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs](https://mlsanity.com/paper/1903.08247/) (2019)
- [On closeness to k-wise uniformity](https://mlsanity.com/paper/1806.03569/) (2018)
- [Is the space complexity of planted clique recovery the same as that of detection?](https://mlsanity.com/paper/2008.12825/) (2020)

## Abstract (arXiv)

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)