BEGIN:VCALENDAR VERSION:2.0 X-WR-CALNAME;VALUE=TEXT:Probabilitas Seminar: Vinod Vaikunthanathan PRODID:-//Harvard events data//EN BEGIN:VEVENT UID:event_1636416_0 SUMMARY:Probabilitas Seminar: Vinod Vaikunthanathan DESCRIPTION:

The Probabilitas Seminar series focuses on high-dimensional problems that combine statistics, probability, artificial intelligence, information theory, computer science, and other related fields. The upcoming seminar takes place on Tuesday, November 11th, at 1:30pm in Science Center 705. This week's speaker will be Vinod Vaikunathanathan of MIT's EECS (Electrical Engineering and Computer Science) and CSAIL (Computer Science and Artificial Intelligence Laboratory).

Title: Lattices and the Computational Hardness of Statistical Problems

Abstract:
I will describe some recent results that shed light on the computational complexity of central problems in statistics and discrepancy theory through the lens of integer lattices. In particular, I will show the computational hardness of the problem of learning Gaussian mixtures; the symmetric binary perceptron problem; and the number partitioning problem, assuming the *worst-case* hardness of shortest-vector-type problems on integer lattices.

Time permitting, I will also describe a recent work that uses the assumed computational hardness of a statistical problem for a constructive purpose. In particular, I will show how to use the assumed pseudorandomness of the Kac walk to speed up algorithms that rely on multiplication by random matrices.

The talk is based on the following papers with Neekon Vafa and others.

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

https://arxiv.org/pdf/2501.16517

https://arxiv.org/pdf/2504.09331

https://arxiv.org/pdf/2502.13065

Topic: Vinod Vaikuntanathan seminar

Time: Nov 11, 2025 01:30 PM Eastern Time (US and Canada)

Join Zoom meeting

https://harvard.zoom.us/j/96164400633?pwd=aEaYT4Sx0ZhVKSVZ2lsBOaeX42LweS.1

Password: 511504

Join by telephone (use any number to dial in)

+1 312 626 6799