PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Daniel Kane (UCSD)
Monday, May 5th 2025, 2-3pm
Abstract:
We discuss information-computation tradeoffs and the models commonly used to provide evidence of computational hardness for statistical problems. In particular, we define low degree tests and their stronger but more difficult cousin PTF tests. Finally, we discuss recent results providing the first non-trivial lower bounds against PTF tests.
Based on joint work with Ilias Diakonikolas, Sihan Liu and Thanasis Pittas.