BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Tselil Schramm (Stanford University) DTSTART:20210309T153000Z DTEND:20210309T163000Z DTSTAMP:20260423T021414Z UID:OAGAS/57 DESCRIPTION:Title: C omputational Barriers to Estimation from Low-Degree Polynomials\nby Ts elil Schramm (Stanford University) as part of Online asymptotic geometric analysis seminar\n\n\nAbstract\nOne fundamental goal of high-dimensional s tatistics 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 computa tional complexity: it has been demonstrated in various settings that low-d egree polynomials of the data can match the statistical performance of the best known polynomial-time algorithms for detection. But prior work has f ailed to address settings in which there is a "detection-recovery gap" and detection is qualitatively easier than recovery.\n\nIn this talk\, I'll d escribe a recent result in which we extend the method of low-degree polyno mials to address recovery problems. As applications\, we resolve (in the l ow-degree framework) open problems about the computational complexity of r ecovery for the planted submatrix and planted dense subgraph problems.\n\n Based on joint work with Alex Wein.\n LOCATION:https://researchseminars.org/talk/OAGAS/57/ END:VEVENT END:VCALENDAR