New techniques establish sharp lower bounds ruling out low-degree polynomial estimation at the BBP and Kesten-Stigum thresholds for planted submatrix, dense subgraph, spiked Wigner, and stochastic block models.
Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
verdicts
UNVERDICTED 2representative 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.
citing papers explorer
-
Sharp Phase Transitions in Estimation with Low-Degree Polynomials
New techniques establish sharp lower bounds ruling out low-degree polynomial estimation at the BBP and Kesten-Stigum thresholds for planted submatrix, dense subgraph, spiked Wigner, and stochastic block models.
-
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.