The 2026 Gödel Prize is awarded to:

• Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust Estimators in High Dimensions without the Computational Intractability. SIAM Journal on Computing, 48(2): 742-864, 2019.

This paper resolves a longstanding problem in robust statistics: whether one can efficiently learn a high-dimensional distribution in the presence of adversarial corruptions without suffering dimension-dependent degradation in accuracy. In a breakthrough result, the authors give polynomial-time algorithms whose error guarantees are independent of the dimension. Before this work, known approaches were either computationally intractable in high dimensions (such as the Tukey median) or had error guarantees that degraded polynomially with the dimension. At the core of the contribution is a striking and elegant principle: if corruptions significantly distort low-order empirical moments (such as the empirical mean), then they must also induce anomalously large spectral structure in higher-order empirical moments (such as the second moment), and this structure can be exploited algorithmically to detect and remove corrupted points.

The paper fundamentally changed our understanding of what is algorithmically possible in robust high-dimensional learning. It introduced tools and ideas that became central to a broad subsequent literature, and helped launch modern algorithmic high-dimensional robust statistics, with major impact across theoretical computer science, statistics, and machine learning.

Award Committee:

Mikołaj Bojańczyk (chair, University of Warsaw)
Artur Czumaj (University of Warwick)
Yuval Ishai (Technion)
Anna Karlin (University of Washington)
Jon Kleinberg (Cornell University)
Marta Kwiatkowska (University of Oxford)