In 2019, a team of researchers including Allen School professor and alum Jerry Li (B.S., ‘13) proved that a broad class of high-dimensional statistical problems can be both efficiently and robustly solved, even when some of the data has been corrupted. The result, described in the groundbreaking paper “Robust Estimators in High Dimensions without the Computational Intractability,” solved a foundational problem in robust statistics that had remained open since the 1960s — and transformed the field in the process.
“The suite of techniques that the paper introduced have now become the cornerstone of a subfield called ‘algorithmic robust statistics,’ and the community has been able to use them to obtain robust estimators for many settings beyond the original paper in statistics, theoretical computer science, and machine learning,” Li said.
At the International Colloquium on Automata, Languages, and Programming (ICALP 2026) last month, Li and his collaborators were awarded the 2026 Gödel Prize for their landmark work. The prize, named for mathematician and logician Kurt Gödel, recognizes outstanding papers in theoretical computer science. “The paper fundamentally changed our understanding of what is algorithmically possible in robust high-dimensional learning,” the award committee wrote.
Prior to this work, researchers struggled with a tradeoff. “All previously known algorithms were either computationally intractable, or their estimators gave useless error guarantees in high dimensions,” Li explained. This meant that in high-dimensional settings with datasets containing thousands of variables, algorithms could either be robust or computationally efficient.
Instead, Li and his collaborators showed that it was possible to achieve both. The researchers introduced the first algorithm for basic estimation problems in high dimensional settings, such as learning the mean of a distribution, that was computationally efficient and also achieves the right statistical guarantees in the presence of a small fraction of potentially arbitrary outliers.
The suite of techniques that the paper introduced have now become the cornerstone of a subfield called ‘algorithmic robust statistics.’
Their results have helped researchers obtain reliable estimators in both theoretical and real-world settings. For example, modern high-dimensional datasets such as those containing medical or financial data can often contain corrupted or unreliable entries from measurement errors, outliers or other issues. Alongside their algorithm, the researchers also developed a broader framework for both detecting and filtering corrupted data.
Li completed this work while a Ph.D. student at the Massachusetts Institute of Technology and intern at Microsoft Research Cambridge. Additional authors include Ilias Diakonikolas, faculty at University of Wisconsin-Madison; Gautam Kamath, faculty at the University of Waterloo; Daniel Kane, faculty at the University of California San Diego; Ankur Moitra, faculty at MIT; and Alistair Stewart, postdoc at the University of Southern California.
The Gödel Prize is awarded annually by the European Association for Theoretical Computer Science and the ACM Special Interest Group on Algorithms and Computation Theory.
Read the full paper here and learn more about the 2026 Gödel Prize.