[Theory] [TTIC Talks] 10/24 Research at TTIC: Jeff Xu, TTIC

[Brandie Jones via Theory]

*When:         *October 24th *at 11am CT  *


*Where:*        Talk will be given *live, in-person* at

                       TTIC, 6045 S. Kenwood Avenue

                        5th Floor, Room 530


*Virtually:*    via Panopto (Livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=fa51bcae-403d-4e1d-b1c8-b31a00f2af6d>
)

*Who:*            Jeff Xu, TTIC

*Title:*            Smooth Tradeoff for Tensor PCA via Sharp Matrix Bounds

*Abstract: *     Tensor Principle Component Analysis (PCA) is a canonical
problem in high-dimensional statistical inferences. Prior works have shown
the success of various spectral algorithms essentially matching the
conjectured computational thresholds for this problem, and it is known that
(at least) in the sub-exponential time regime, similar to random CSP
refutation, Tensor PCA exhibits a smooth tradeoff in signal-strength and
runtime: increasing run-time allows one to detect a weaker signal. However,
it is not clear whether such tradeoff appears in the polynomial-time
regime, and establishing such a trade-off has crucial implications for
quantum speed-ups.  Recently, the work of Bandeira et al. makes partial
progress by establishing a smooth trade-off in a “limited" polytime regime
via techniques from free probability.  In this talk, I will sketch a
self-contained combinatorial argument for resolving this conjecture in its
full generality, and highlight some open question along this direction.

Based on a joint work with Pravesh K. Kothari that can be found in
https://arxiv.org/abs/2510.03061.



***********************************************************************************************

*Research at TTIC Seminar Series*



TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended for students
seeking research topics and advisors, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.



*Brandie Jones *
*Executive **Administrative Assistant*
*Outreach Administrator *
Toyota Technological Institute
6045 S. Kenwood Avenue
Chicago, IL  60637
www.ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20251017/28c32f69/attachment-0001.html>