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.
Low- degree lower bounds via almost orthonormal bases
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
years
2026 3verdicts
UNVERDICTED 3representative citing papers
Establishes sharp low-degree estimation thresholds in planted hypergraphs and tensor PCA, resolving open hardness questions and yielding polynomial-time algorithms above thresholds.
A model-independent framework converts mild low-degree testing advantages into conditional computational lower bounds for recovery tasks, recovering prior results for planted submatrix and SBM while providing new evidence for detection-recovery gaps in angular synchronization and multi-layer models.
citing papers explorer
-
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.
-
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.
-
Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
A model-independent framework converts mild low-degree testing advantages into conditional computational lower bounds for recovery tasks, recovering prior results for planted submatrix and SBM while providing new evidence for detection-recovery gaps in angular synchronization and multi-layer models.