The minimax rate for estimating d-th order moment tensors is sqrt(p/n) wedge 1, while low-degree evidence shows detection of vanishing cumulants is hard for n much less than p to the d/2, creating a reverse detection-estimation gap.
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensional inference problems. In short, the method posits that a certain quantity -- the second moment of the low-degree likelihood ratio -- gives insight into how much computational time is required to solve a given hypothesis testing problem, which can in turn be used to predict the computational hardness of a variety of statistical inference tasks. While this method originated in the study of the sum-of-squares (SoS) hierarchy of convex programs, we present a self-contained introduction that does not require knowledge of SoS. In addition to showing how to carry out predictions using the method, we include a discussion investigating both rigorous and conjectural consequences of these predictions. These notes include some new results, simplified proofs, and refined conjectures. For instance, we point out a formal connection between spectral methods and the low-degree likelihood ratio, and we give a sharp low-degree lower bound against subexponential-time algorithms for tensor PCA.
years
2026 3representative citing papers
SYK disorder is shown to be an approximate unitary k-design for poly(N) k; under the planted-SYK hardness conjecture this yields gravitationally pseudorandom unitaries, implying cryptographic censorship in JT gravity with the regularized maximal geodesic length as distinguisher.
This review synthesizes representative advances in high-dimensional statistics, highlights common themes and open problems, and points to key entry works.
citing papers explorer
-
Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors
The minimax rate for estimating d-th order moment tensors is sqrt(p/n) wedge 1, while low-degree evidence shows detection of vanishing cumulants is hard for n much less than p to the d/2, creating a reverse detection-estimation gap.
-
Pseudorandom Dynamics in the SYK Model and Cryptographic Censorship in JT Gravity
SYK disorder is shown to be an approximate unitary k-design for poly(N) k; under the planted-SYK hardness conjecture this yields gravitationally pseudorandom unitaries, implying cryptographic censorship in JT gravity with the regularized maximal geodesic length as distinguisher.
-
High-Dimensional Statistics: Reflections on Progress and Open Problems
This review synthesizes representative advances in high-dimensional statistics, highlights common themes and open problems, and points to key entry works.