# Notes on computational-to-statistical gaps: predictions using statistical physics

arXiv: https://arxiv.org/abs/1803.11132 · HTML: https://mlsanity.com/paper/1803.11132/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2018.

## Built on by (most cited first, 22 of 22)

- [All Roads Lead to Likelihood: The Value of Reinforcement Learning in Fine-Tuning](https://mlsanity.com/paper/2503.01067/) (2025)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [Long Random Matrices and Tensor Unfolding](https://mlsanity.com/paper/2110.10210/) (2021)
- [Injectivity of ReLU networks: perspectives from statistical physics](https://mlsanity.com/paper/2302.14112/) (2023)
- [Optimal Algorithms for the Inhomogeneous Spiked Wigner Model](https://mlsanity.com/paper/2302.06665/) (2023)
- [Landscape analysis of an improved power method for tensor decomposition](https://mlsanity.com/paper/2110.15821/) (2021)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Spectral Phase Transition and Optimal PCA in Block-Structured Spiked models](https://mlsanity.com/paper/2403.03695/) (2024)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximation](https://mlsanity.com/paper/2402.03169/) (2024)
- [Cryptographic Hardness of Score Estimation](https://mlsanity.com/paper/2404.03272/) (2024)
- [Bayesian reconstruction of memories stored in neural networks from their connectivity](https://mlsanity.com/paper/2105.07416/) (2021)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Fundamental limits of Non-Linear Low-Rank Matrix Estimation](https://mlsanity.com/paper/2403.04234/) (2024)
- [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026)
- [Unrolled denoising networks provably learn optimal Bayesian inference](https://mlsanity.com/paper/2409.12947/) (2024)
- [Bayesian Inference with Nonlinear Generative Models: Comments on Secure Learning](https://mlsanity.com/paper/2201.09986/) (2022)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)

## Abstract (arXiv)

In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems. These are regimes in which the underlying statistical problem is information-theoretically possible although no efficient algorithm exists, rendering the problem essentially unsolvable for large instances. The methods we describe here are based on mature, albeit non-rigorous, tools from statistical physics. These notes are based on a lecture series given by the authors at the Courant Institute of Mathematical Sciences in New York City, on May 16th, 2017.