Professor Gautam Kamath and his colleagues, Ilias Diakonikolas, Daniel Kane, Jerry Li, Ankur Moitra and Alistair Stewart, have been awarded the 2026 Gödel Prize for their landmark paper, Robust Estimators in High-Dimensions without the Computational Intractability.
The Gödel Prize recognizes outstanding contributions to theoretical computer science and is widely regarded as the field’s most prestigious honour. Awarded annually since 1993, the prize is named for Kurt Gödel in recognition of his major contributions to mathematical logic and his interest in what became known as the famous P versus NP question. The award includes a cash prize of $5,000 USD.
“This is a truly wonderful and well-deserved recognition,” said Raouf Boutaba, University Professor and Director of the Cheriton School of Computer Science. “It’s gratifying to see Gautam and his collaborators recognized for their pioneering work on computationally efficient algorithms for fundamental estimation tasks under constraints of robustness. Receipt of this year’s Gödel Prize, so soon after Gautam’s 2026 Presburger Award, is further evidence of the significant and lasting impact of this research.”
Gautam Kamath is an Assistant Professor at the Cheriton School of Computer Science, a Canada CIFAR AI Chair at the Vector Institute, and a member of Waterloo’s Cybersecurity and Privacy Institute. An expert in algorithms, statistics and machine learning, his research focuses on modern data analysis under constraints such as differential privacy and robustness.
As of June 2026, his publications have been cited almost 7,000 times, with an h-index of 41, according to Google Scholar.
Robust Estimators in High Dimensions Without the Computational Intractability is a landmark paper in theoretical computer science. It resolved a foundational problem that had remained elusive for decades: whether high-dimensional robust unsupervised learning can be carried out efficiently without suffering dimension-dependent degradation in accuracy.
Before this work, understanding of the computational landscape in robust learning was limited. Even for the most basic problem of mean estimation, known statistically robust estimators were computationally intractable in high dimensions, while all known computationally efficient methods incurred error guarantees that deteriorated polynomially with the dimension.
Robust Estimators in High Dimensions without the Computational Intractability overcame this barrier. It provided the first efficient algorithms with dimension-independent error guarantees for several central high-dimensional distribution classes, and introduced a general methodology to detect and correct corruptions in high dimensions that became a blueprint for a large subsequent literature.
The field that grew out of this breakthrough is now supported by a substantial expository and educational infrastructure, including graduate-level surveys, book chapters, a research monograph, and courses at several institutions.
Presented originally at FOCS 2016, the 57th Annual Symposium on Foundations of Computer Science, this highly acclaimed paper was subsequently invited to several prestigious venues, among them the SIAM Journal on Computing’s Special Issue for FOCS 2016, Highlights of Algorithms 2017, and Communications of the ACM Research Highlights. As of June 2026, it has been cited more than 670 times.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。