View source for 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|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|average-case complexity]], statistical physics, and the theory of [[Sum-of-Squares Hierarchy|sum-of-squares proofs]].

[[Category:Mathematics]] [[Category:Computer Science]] [[Category:Systems]]