Tselil Schramm, Stanford University

Abstract: One fundamental goal of high-dimensional statistics is to detect and recover structure from noisy data. But even for simple settings (e.g. a planted low-rank matrix perturbed by noise), the computational complexity of estimation is sometimes poorly understood. A growing body of work studies low-degree polynomials as a proxy for computational complexity: it has been demonstrated in various settings that low-degree polynomials of the data can match the statistical performance of the best known polynomial-time algorithms for detection. But prior work has failed to address settings in which there is a "detection-recovery gap" and detection is qualitatively easier than recovery. In this talk, I'll describe a recent result in which we extend the method of low-degree polynomials to address recovery problems. As applications, we resolve (in the low-degree framework) open problems about the computational complexity of recovery for the planted submatrix and planted dense subgraph problems. Based on joint work with Alex Wein.