Lattices and the Hardness of Statistical Problems

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 algorithms, assuming the worst-case hardness of lattice problems.
The talk is based on the following papers with Aparna Gupte and Neekon Vafa.

https://arxiv.org/pdf/2204.02550.pdf

https://arxiv.org/pdf/2402.14645.pdf

Bio:
Vinod Vaikuntanathan is a professor of computer science at MIT and the chief cryptographer at Duality Technologies. His research is in the foundations of cryptography and its applications to theoretical computer science at large. He is known for his work on fully homomorphic encryption, a powerful cryptographic primitive that enables complex computations on encrypted data, as well as lattice-based cryptography, which lays down a new mathematical foundation for cryptography in the post-quantum world. Recently, he has been interested in the interactions of cryptography with quantum computing, as well as with statistics and machine learning. Vinod’s work has been recognized with several awards including the Simons Investigator Award (2023) and Gödel Prize (2022).