# Universality of Computational Lower Bounds for Submatrix Detection

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2019.

## Built on by (most cited first, 13 of 13)

- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds](https://mlsanity.com/paper/2506.06259/) (2025)
- [A Goodness-of-fit Test on the Number of Biclusters in a Relational Data Matrix](https://mlsanity.com/paper/2102.11658/) (2021)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Computationally efficient reductions between some statistical models](https://mlsanity.com/paper/2402.07717/) (2024)
- [Testing Dependency of Weighted Random Graphs](https://mlsanity.com/paper/2409.14870/) (2024)
- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

In the general submatrix detection problem, the task is to detect the presence of a small k × k submatrix with entries sampled from a distribution P in an n × n matrix of samples from Q. This formulation includes a number of well-studied problems, such as biclustering when P and Q are Gaussians and the planted dense subgraph formulation of community detection when the submatrix is a principal minor and P and Q are Bernoulli random variables. These problems all seem to exhibit a universal phenomenon: there is a statistical-computational gap depending on P and Q between the minimum k at which this task can be solved and the minimum k at which it can be solved in polynomial time. Our main result is to tightly characterize this computational barrier as a tradeoff between k and the KL divergences between P and Q through average-case reductions from the planted clique conjecture. These computational lower bounds hold given mild assumptions on P and Q arising naturally from classical binary hypothesis testing. Our results recover and generalize the planted clique lower bounds for Gaussian biclustering in Ma-Wu (2015) and Brennan et al. (2018) and for the sparse and general regimes of planted dense subgraph in Hajek et al. (2015) and Brennan et al. (2018). This yields the first universality principle for computational lower bounds obtained through average-case reductions.