# Average-Case Communication Complexity of Statistical Problems

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 3 Jul 2021.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [Notes on computational-to-statistical gaps: predictions using statistical physics](https://mlsanity.com/paper/1803.11132/) (2018)
- [Sum-of-squares lower bounds for planted clique](https://mlsanity.com/paper/1503.06447/) (2015)
- [Querying a Matrix through Matrix-Vector Products](https://mlsanity.com/paper/1906.05736/) (2019)
- [Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems](https://mlsanity.com/paper/2006.14015/) (2020)
- [Finding a planted clique by adaptive probing](https://mlsanity.com/paper/1903.12050/) (2019)
- [Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries](https://mlsanity.com/paper/1908.06130/) (2019)
- [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)
- [Quick Detection of High-degree Entities in Large Directed Networks](https://mlsanity.com/paper/1410.0571/) (2014)

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

- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Low-degree phase transitions for detecting a planted clique in sublinear time](https://mlsanity.com/paper/2402.05451/) (2024)
- [Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods](https://mlsanity.com/paper/2510.16609/) (2025)

## Abstract (arXiv)

We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation is to understand the statistical-computational trade-offs in streaming, sketching, and query-based models. Communication complexity is the main tool for proving lower bounds in these models, yet many prior results do not hold in an average-case setting. We provide a general reduction method that preserves the input distribution for problems involving a random graph or matrix with planted structure. Then, we derive two-party and multi-party communication lower bounds for detecting or finding planted cliques, bipartite cliques, and related problems. As a consequence, we obtain new bounds on the query complexity in the edge-probe, vector-matrix-vector, matrix-vector, linear sketching, and mathbbF2-sketching models. Many of these results are nearly tight, and we use our techniques to provide simple proofs of some known lower bounds for the edge-probe model.