Friday, April 23, 2021 at 3:30pm to 4:30pm
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.
Please see your email to join via zoom