mlsanityData to 7 Oct 2026

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

arXiv 1806.07508 ↗First posted 19 Jun 2018cs.CC cs.DS cs.ITcited by 35

Not on the map. Why?

Abstract (arXiv)

The prototypical high-dimensional statistics problem entails finding a structured signal in noise. Many of these problems exhibit an intriguing phenomenon: the amount of data needed by all known computationally efficient algorithms far exceeds what is needed for inefficient algorithms that search over all possible structures. A line of work initiated by Berthet and Rigollet in 2013 has aimed to explain these statistical-computational gaps by reducing from conjecturally hard average-case problems in computer science. However, the delicate nature of average-case reductions has limited the applicability of this approach. In this work we introduce several new techniques to give a web of average-case reductions showing strong computational lower bounds based on the planted clique conjecture using natural problems as intermediates. These include tight lower bounds for Planted Independent Set, Planted Dense Subgraph, Sparse Spiked Wigner, Sparse PCA, a subgraph variant of the Stochastic Block Model and a biased variant of Sparse PCA. We also give algorithms matching our lower bounds and identify the information-theoretic limits of the models we consider.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Jun 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 6; 2023: 10; 2024: 5; 2025: 7; 2026: 1.

35 papers.

Sort:

By area:

  1. 2023Sampling, Diffusions, and Stochastic Localizationcited by 38
  2. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  3. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  4. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 17
  5. 2023Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initializationcited by 10
  6. 2023Detection of Dense Subhypergraphs by Low-Degree Polynomialscited by 7
  7. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  8. 2022Higher degree sum-of-squares relaxations robust against oblivious outlierscited by 6
  9. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  10. 2022Is it easier to count communities than find them?cited by 4
  11. 2023Detection-Recovery Gap for Planted Dense Cyclescited by 4
  12. 2024On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariancecited by 4
23 more
  1. 2021Random Subgraph Detection Using Queriescited by 3
  2. 2024Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testingcited by 3
  3. 2025Phase Transition for Stochastic Block Model with more than √n Communities (II)cited by 3
  4. 2021Inferring Hidden Structures in Random Graphscited by 2
  5. 2022Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designscited by 2
  6. 2023Planted Bipartite Graph Detectioncited by 2
  7. 2023Sparse PCA Beyond Covariance Thresholdingcited by 2
  8. 2023Bayes optimal learning in high-dimensional linear regression with network side informationcited by 2
  9. 2024The graph alignment problem: fundamental limits and efficient algorithmscited by 2
  10. 2025Low degree conjecture implies sharp computational thresholds in stochastic block modelcited by 2
  11. 2025Computational bottlenecks for denoising diffusionscited by 2
  12. 2022Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learningcited by 1
  13. 2023Do algorithms and barriers for sparse principal component analysis extend to other structured settings?cited by 1
  14. 2025Optimal community detection in dense bipartite graphscited by 1
  15. 2021A Goodness-of-fit Test on the Number of Biclusters in a Relational Data Matrixcited by 0
  16. 2021Logspace Reducibility From Secret Leakage Planted Cliquecited by 0
  17. 2023Statistical and computational rates in high rank tensor estimationcited by 0
  18. 2024Low-degree phase transitions for detecting a planted clique in sublinear timecited by 0
  19. 2024Computationally efficient reductions between some statistical modelscited by 0
  20. 2025Robust Detection of Planted Subgraphs in Semi-Random Modelscited by 0
  21. 2025Phase Transition for Stochastic Block Model with more than √n Communitiescited by 0
  22. 2025Statistical and computational challenges in rankingcited by 0
  23. 2026Low-Degree Method Fails to Predict Robust Subspace Recoverycited by 0