College of LAS Events

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, learning 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. This perspective raises numerous open problems and directions, and I will try to highlight several of them. Joint work with Alina Harbuzova. 

Bio: Guy Bresler is an Associate Professor of Electrical Engineering and Computer Science at MIT and a member of LIDS, IDSS, Center for Statistics, and the Theory of Computation Group. He received his PhD from the Department of EECS at UC Berkeley and MS in Mathematics and BS in ECE at the University of Illinois at Urbana-Champaign. His research aims to elucidate relationships between combinatorial properties, information structure, and computational tractability in statistical inference and machine learning.