Computational Gap

Computational gaps in statistical inference problems explore the discrepancy between the information-theoretically achievable performance and the performance of computationally efficient algorithms. Current research focuses on identifying these gaps in various models, including sparse linear regression, tensor decomposition, and Gaussian mixture models, often employing techniques like low-degree polynomials and statistical queries to establish lower bounds on the computational complexity. Understanding these gaps is crucial for developing more efficient algorithms and for setting realistic expectations about the solvability of high-dimensional statistical problems in practice, impacting fields ranging from machine learning to signal processing.