Sharp Phase Transitions in Estimation with Low-Degree Polynomials

Youngtak Sohn, Alexander S. Wein

High-dimensional planted problems, such as finding a hidden dense subgraph within a random graph, often exhibit a gap between statistical and computational feasibility. While recov…