Average-Case Communication Complexity of Statistical Problems
This work addresses the challenge of proving lower bounds in average-case settings for researchers in theoretical computer science and statistics, offering incremental improvements by extending prior results to more realistic scenarios.
The paper tackles the problem of understanding statistical-computational trade-offs in models like streaming and sketching by studying average-case communication complexity for statistical problems such as planted clique and sparse PCA. It provides a general reduction method to derive communication lower bounds, leading to new, nearly tight bounds on query complexity in various models.
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 $\mathbb{F}_2$-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.