No article text was recorded for this version.
computational-statistical gap (statistical-computational gap)
Version 1 of 11,177 papers1,904 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Complexity Theoretic Lower Bounds for Sparse Principal Component Detection
- Blog: Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
- Blog: Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap
- Blog: Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
- Blog: Statistical-Computational Phase Transitions in Planted Models: The High-Dimensional Setting
- Blog: High-Dimensional Gaussian Mean Estimation under Realizable Contamination
- Blog: Statistical and Computational Rates in Graph Logistic Regression
- Blog: Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap
- Blog: Sparse PCA Beyond Covariance Thresholding
- Blog: On the Fundamental Limits of Exact Inference in Structured Prediction
- Blog: Preface
- Blog: Cryptographic Hardness of Score Estimation
- Blog: Statistical and Computational Limits for Sparse Matrix Detection
- Blog: Correlation Detection in Trees for Planted Graph Alignment
- Blog: Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
- Blog: Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
- Blog: Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
- Blog: Computational lower bounds for multi-frequency group synchronization
- Blog: All-or-Nothing Phenomena: From Single-Letter to High Dimensions
- Blog: Breaking the $1/\sqrtn$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
- Blog: The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
- Blog: Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
- Blog: Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
- Blog: Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
- Blog: Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
- Blog: More data speeds up training time in learning halfspaces over sparse vectors
- Blog: On Detection and Structural Reconstruction of Small-World Random Networks
- Blog: Sparse Linear Regression when Noises and Covariates are Heavy-Tailed and Contaminated by Outliers
- Blog: Learning Structured Distributions From Untrusted Batches: Faster and Simpler
- Blog: Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
- Blog: Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
- Blog: Learning Multivariate Log-concave Distributions
- Blog: Computational Lower Bounds for Sparse PCA
- Blog: Performance of Rank-One Tensor Approximation on Incomplete Data
- Blog: Using Black-Box Compression Algorithms for Phase Retrieval
- Blog: Information-theoretic thresholds for community detection in sparse networks
- Blog: Outlier Robust Mean Estimation with Subgaussian Rates via Stability
- Blog: On Computationally Efficient Learning of Exponential Family Distributions
- Blog: The Complexity of Sparse Tensor PCA
- Blog: Estimating Principal Components under Adversarial Perturbations
- Blog: Detection of L∞ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion
- Blog: Weak Recovery Threshold for the Hypergraph Stochastic Block Model
- Blog: Sparse PCA via Covariance Thresholding
- Blog: Message-passing algorithms for synchronization problems over compact groups
- Blog: Statistical Estimation: From Denoising to Sparse Regression and Hidden Cliques
- Blog: Bayesian Inference With Nonlinear Generative Models: Comments on Secure Learning
- Blog: Parallels Between Phase Transitions and Circuit Complexity?
- Blog: Clustering a Mixture of Gaussians with Unknown Covariance
- Blog: More data speeds up training time in learning halfspaces over sparse vectors
- Blog: All-or-Nothing Phenomena: From Single-Letter to High Dimensions.
- Blog: Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap
- Blog: Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data
- Blog: Weak Recovery Threshold for the Hypergraph Stochastic Block Model
- Blog: Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs
- Blog: Revisiting Agnostic Boosting
- Blog: Detection of Planted Solutions for Flat Satisfiability Problems
- Blog: Bayesian reconstruction of memories stored in neural networks from their connectivity
- Blog: Information-Theoretic Characterization of Sparse Recovery
- Blog: Low-rank Matrix Estimation with Inhomogeneous Noise
- Blog: How Hard is Robust Mean Estimation?
Showing 60 of 1,177 papers.
History & citation
Current · Permanent link
- Average Case Reductions for Statistical Computational Gaps merged into this direction (83% overlap)
- Fisher Information Universality in High Dimensional Inference merged into this direction (69% overlap)
- Rigorous Limits of High-Dimensional Inference via the Replica Method merged into this direction (59% overlap)
- Computational and Statistical Phase Transitions in Inference merged into this direction (97% overlap)
- Statistical Computational Gaps in Permuted Matrix Estimation merged into this direction (100% overlap)
- The Statistical Computational Gap in High Dimensional Sparse Estimation merged into this direction (88% overlap)
- Statistical-to-Computational Gaps in High-Dimensional Inference merged into this direction (85% overlap)
- Statistical Computational Gaps in Correlated Graph Alignment merged into this direction (81% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_computational_statistical_gap_statistica_3c721a00,
title = {computational-statistical gap (statistical-computational gap)},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/computational-statistical-gap-statistical-computational-gap/rdr_3c721a001eb94d619603d6bc0eaad5dd},
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_computational_statistical_gap_statistica_3c721a00_v1,
title = {computational-statistical gap (statistical-computational gap)},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/computational-statistical-gap-statistical-computational-gap/rdr_3c721a001eb94d619603d6bc0eaad5dd/v/1},
note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}