Average Case Reductions for Statistical Computational Gaps

This direction is merged into another direction: computational-statistical gap (statistical-computational gap). Its last version stays readable and citable here.

Version 1 of 129 papers34 conceptsfrozen 2026-10-04

In classical complexity theory, we prove a problem is hard by showing that if you could solve it, you could also solve a known difficult problem like 3-SAT. In high-dimensional statistics, a similar phenomenon occurs, but with a twist: problems aren't just "hard" or "easy" in an absolute sense. Instead, they often exhibit a statistical-computational gap.

In these gaps, there is enough data to solve a problem in theory (information-theoretically), but no known algorithm can solve it in polynomial time. To prove these gaps exist, researchers have developed a "web of reductions" for average-case problems, allowing them to transfer hardness from a few foundational conjectures to a vast array of statistical tasks.

The Information-Computation Gap

For many high-dimensional estimation tasks, the amount of data required to make a problem possible is much smaller than the amount required to make it efficiently solvable.

As Matthew S. Brennan and Wasim Huleihel explain in Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure, the field of statistics historically lacked the unified complexity framework that computer science enjoys. Without a way to link different problems, researchers had to prove hardness for every new model—Sparse PCA, Community Detection, or Submatrix Detection—from scratch.

The breakthrough in this field is the use of average-case reductions. By mathematically transforming an instance of a known hard problem into an instance of a target statistical problem, researchers can prove that the target problem must also be hard. If an efficient algorithm existed for the target, it would inadvertently solve the original hard problem.

The Planted Clique Anchor

The "3-SAT" of this average-case world is the Planted Clique problem. In this model, we are given a random graph and asked to find a small, fully connected "clique" hidden within it. While the clique is statistically visible once it reaches a certain size, it is conjectured to be computationally impossible to find if it is smaller than the square root of the number of vertices.

This conjecture serves as the bedrock for the field. For example, Bruce E. Hajek, Yihong Wu 0001, and Jiaming Xu 0002 used reductions from Planted Clique in Computational Lower Bounds for Community Detection on Random Graphs to show that finding communities in networks has a fundamental computational barrier. Similarly, Matthew S. Brennan demonstrated in Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness that the known limits for Sparse PCA are not just a failure of current algorithms, but are tied to the inherent hardness of the Planted Clique problem.

Building the Web of Reductions

The power of this research direction lies in its "reducibility." Once a problem like Sparse PCA is proven hard via Planted Clique, it can then be used as a base to prove the hardness of even more complex problems.

This creates a cascading effect:

  1. From Graphs to Matrices: Reductions transform graph adjacency matrices into spiked covariance matrices to prove limits for Sparse PCA.
  2. From Matrices to Regression: Rares-Darius Buhai and colleagues showed in Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression that the hardness of Sparse PCA implies a sample complexity gap in sparse linear regression.
  3. From Detection to Recovery: Guy Bresler and Tianze Jiang expanded this in Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique, proving that for some problems, it is easy to tell if a signal exists but computationally hard to locate it.

Preserving Hardness Across Distributions

The technical challenge of these reductions is ensuring that the "transformed" data looks like a natural statistical sample. If the reduction produces data that is "too weird," it doesn't prove anything about the real-world statistical problem.

Recent work by Guy Bresler, Mengqi Lou, and Ashwin Pananjady in Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs provides a "toolbox" for this. They use Markov kernels to map simple source distributions (like Gaussians) to complex target distributions while preserving the underlying computational hardness. This allows lower bounds to be transferred across different noise models, such as from Gaussian to Bernoulli distributions, as explored in the "universality" results of Matthew S. Brennan and Wasim Huleihel in Universality of Computational Lower Bounds for Submatrix Detection.

New Frontiers in Generative Models

This framework is now moving beyond simple estimation into modern machine learning. In Computational bottlenecks for denoising diffusions, Andrea Montanari and Viet Vu apply these reductions to diffusion models. They prove that even if a distribution is easy to sample from in theory, a diffusion model may be computationally unable to learn it if the underlying structure is tied to a hard statistical problem like Sparse PCA.

By treating statistical problems as a connected ecosystem rather than isolated challenges, this research direction provides a rigorous way to map the boundaries of what is actually computable in the age of high-dimensional data.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_average_case_reductions_for_statistical__1056101d,
  title = {Average Case Reductions for Statistical Computational Gaps},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/average-case-reductions-for-statistical-computational-gaps/rdr_1056101d783143d8af7ba1046e988949},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_average_case_reductions_for_statistical__1056101d_v1,
  title = {Average Case Reductions for Statistical Computational Gaps},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/average-case-reductions-for-statistical-computational-gaps/rdr_1056101d783143d8af7ba1046e988949/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}