Lattices and the Hardness of Statistical Problems
Vinod Vaikuntanathan (MIT)
E18-304
Abstract: I will describe recent results that (a) show nearly optimal hardness of learning Gaussian mixtures, and (b) give evidence of average-case hardness of sparse linear regression w.r.t. all efficient…