Tata Institute of Fundamental Research

Algorithmically Testing Sub-Gaussianity of High Dimensional Distributions

STCS Seminar
Speaker: Ankit Pensia (CARNEGIE MELLON UNIVERSITY, USA)
Organiser: Vinod M. Prabhakaran
Date: Wednesday, 7 Jan 2026, 11:00 to 12:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract: 
Sub-Gaussian distributions play a central role in statistics, probability, and computer science. A distribution is termed sub-Gaussian if all of its univariate projections have tails that decay faster than a Gaussian. In algorithmic statistics, a central task is the following: given samples from a distribution, decide whether the underlying distribution is sub-Gaussian or heavy-tailed. In high dimensions, this is a challenging problem because sub-Gaussianity requires all univariate projections to be light-tailed, which seemingly necessitates a brute-force search over directions to verify. In this talk, I will describe a structural property of sub-Gaussian distributions that leads to computationally efficient algorithms for a wide range of statistical problems, e.g., clustering, robust estimation, and more. Based on joint work with Ilias Diakonikolas, Sam Hopkins, and Stefan Tiegel.
 
Short Bio: Ankit Pensia is an assistant professor in the Department of Statistics and Data Science at Carnegie Mellon University. Previously, he was a research fellow at the Simons Institute for the Theory of Computing and a Herman Goldstine Postdoctoral Fellow at IBM Research. He obtained his PhD in Computer Science from the University of Wisconsin-Madison. His current research interests include algorithmic robust statistics, high-dimensional probability, distribution testing, and algorithmic stability.