# Is it easier to count communities than find them?

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 22 references that are in the map.
- First posted on arXiv 21 Dec 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [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)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness](https://mlsanity.com/paper/1702.00467/) (2017)
- [Local Statistics, Semidefinite Programming, and Community Detection](https://mlsanity.com/paper/1911.01960/) (2019)
- [Community Detection in Random Networks](https://mlsanity.com/paper/1302.7099/) (2013)

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

- [Precise Error Rates for Computationally Efficient Testing](https://mlsanity.com/paper/2311.00289/) (2023)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Rarity Determines Minimax Rates of Semantic Entropy From Weak Pairwise Judgments With a Known Channel](https://mlsanity.com/paper/2610.17971/) (2026)

## Abstract (arXiv)

Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities. Our methods give the first computational lower bounds for testing between two different ``planted'' distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. ``null'' distribution. We also show a formal relationship between the low--degree frameworks for recovery in a planted model and for testing two planted models.