Webcast Option: https://yale.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=9a9641c5-6fad-4d17-8e8b-b3b700eef933
Title: Average-Case Reductions for k-XOR and Tensor PCA
Abstract: Noisy k-𝖷𝖮𝖱 is the problem of recovering a Boolean vector from noisy linear equations with k non-zero coefficients; it is a foundational problem in complexity theory and cryptography. Tensor PCA is the problem of recovering a vector from its rank one tensor product perturbed by additive Gaussian noise; it is a canonical problem in high-dimensional statistics exhibiting a computational-statistical gap. We consider a family of problems that interpolates between k-𝖷𝖮𝖱 and Tensor PCA and introduce two densifying reductions that increase the number of observed entries while controlling the decrease in signal, and, in particular, reduce any k-𝖷𝖮𝖱 instance at the computational threshold to Tensor PCA at the computational threshold. Additionally, we give new order-reducing maps (e.g., 5 to 4 for k-𝖷𝖮𝖱 and 7 to 4 for Tensor PCA) at fixed entry density. Our results establish a hardness partial order in the space of tensor order and entry density, advancing a unified study of planted tensor models and relationships between them. Joint work with Alina Harbuzova.
3:30pm - Pre-talk meet and greet teatime - 219 Prospect Street, 13 floor, there will be light snacks and beverages in the kitchen area. For more details and upcoming events visit our website at https://statistics.yale.edu/calendar.