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.
The quasi- polynomial low-degree conjecture is false
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
years
2026 5representative citing papers
The paper establishes sharp low-degree thresholds for planted-vs-planted testing in planted submatrix and dense subgraph models that match known recovery thresholds down to the constant.
A public-key encryption scheme with quasi-exponential security is constructed from the conjectured intractability of high-corruption LARP-CSP and kXOR problems, supported by lower bounds and a new error-correcting code.
A near-optimal recovery algorithm for noisy k-XOR achieves the information-theoretic sample scaling with optimal noise dependence and is matched by low-degree lower bounds.
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.
-
Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
The paper establishes sharp low-degree thresholds for planted-vs-planted testing in planted submatrix and dense subgraph models that match known recovery thresholds down to the constant.
-
Public Key Encryption from High-Corruption Constraint Satisfaction Problems
A public-key encryption scheme with quasi-exponential security is constructed from the conjectured intractability of high-corruption LARP-CSP and kXOR problems, supported by lower bounds and a new error-correcting code.
-
Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
A near-optimal recovery algorithm for noisy k-XOR achieves the information-theoretic sample scaling with optimal noise dependence and is matched by low-degree lower bounds.
-
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.