Establishes sharp low-degree estimation thresholds in planted hypergraphs and tensor PCA, resolving open hardness questions and yielding polynomial-time algorithms above thresholds.
The landscape of the p lanted clique problem: Dense subgraphs and the overlap gap property
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
math.ST 2verdicts
UNVERDICTED 2representative citing papers
The low-degree likelihood ratio method predicts computational hardness of hypothesis testing problems, with new connections to spectral methods and a lower bound for tensor PCA.
citing papers explorer
-
Low-degree estimation thresholds in planted hypergraphs and tensor PCA
Establishes sharp low-degree estimation thresholds in planted hypergraphs and tensor PCA, resolving open hardness questions and yielding polynomial-time algorithms above thresholds.
-
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
The low-degree likelihood ratio method predicts computational hardness of hypothesis testing problems, with new connections to spectral methods and a lower bound for tensor PCA.