Statistical-Computational Gap

The statistical-computational gap is the phenomenon whereby a learning or inference problem is information-theoretically solvable — given unlimited computational resources, the correct answer can be identified — yet no efficient algorithm is known or believed to exist. The gap reveals that data and computation are not interchangeable resources: more data cannot compensate for computational intractability, and faster algorithms cannot compensate for insufficient information. The two constraints operate independently, and the hardest problems in modern machine learning sit precisely in the gap between them.

Classic examples include the planted clique problem, where a hidden clique of size k in a random graph can be detected information-theoretically for k as small as O(log n) but no polynomial-time algorithm is known for k = o(√n); and sparse PCA, where the statistical threshold for recovery falls below the algorithmic threshold. The gap is conjectured to be fundamental, arising from geometric properties of high-dimensional spaces that distinguish what is statistically detectable from what is computationally accessible. Understanding this gap requires tools from average-case complexity, statistical physics, and the theory of sum-of-squares proofs.