Renowned mathematician and artificial intelligence researcher Sebastian Pokutta has been awarded the prestigious Gödel Prize along with his co-authors and colleagues for their influential work in combinatorial optimization. Their paper, “Exponential Lower Bounds for Polytopes in Combinatorial Optimization,” published in the Journal of the ACM in 2015, has been recognized for its groundbreaking contribution. 

Pokutta was delighted to receive the Gödel Prize and commented: “I’m very humbled and proud to receive the Gödel Prize together with my colleagues. The awarded paper fundamentally changes our understanding of hard computational problems, particularly the notorious Travelling Salesman Problem (TSP). Researchers have sought to create an efficient linear program to solve TSP for decades. Successful execution of such an endeavor would have profound implications for algorithmic efficiency across numerous computational challenges. However, building upon Yannakakis’ work from 1988, our paper conclusively demonstrated that this approach is destined to fail.” The team proved that any linear program describing the TSP must be exponentially large, thus putting a definitive boundary on applying linear programming for these complex problems.

Pokutta shares this honor with co-authors Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf and colleague Thomas Rothvoss for his work ruling out efficient linear programs for the matching polytope. Thus, the award reflects a collaborative effort that has made significant strides in the field of theoretical computer science. The Gödel Prize will be officially awarded at the 55th Annual ACM Symposium on the Theory of Computing, which takes place on 20-23 June 2023 in Orlando, Florida.

Sebastian Pokutta is the Vice President of the Zuse Institute Berlin (ZIB), a Professor of Mathematics at TU Berlin, and a most committed MATH+ member. His research interests lie at the intersection of artificial intelligence and optimization, combining machine learning with discrete optimization techniques and the theory of extended formulations. This groundbreaking work explores the limits of computation in alternative models of complexity.

© Beate Rogler / MATH+

Within MATH+, Pokutta currently heads numerous research projects of the MATH+ Emerging Field “Extracting Dynamical Laws From Complex Data” and the Application Area “Next Generation Networks,” that are highly relevant for solving constrained optimization:

• • AA3-7 “Beyond the Worst-Case: Data-Dependent Rates in Learning and Optimization“
  • AA3-15 “Convex Solver Adaptivity for Mixed-Integer Optimization“
  • EF1-14 “Sparsity and Sample-Size Efficiency in Structured Learning“
  • EF 1-23 “On a Frank-Wolfe Approach for Abs-Smooth Optimization“

All these projects deal with various aspects of so-called Conditional Gradient methods that offer solutions with additional properties such as sparsity, a concept of high relevance in machine learning.

Moreover, he also serves on the Board of MATH+ and is Steering Committee Chair of the MATH+ Activity Group “Mathematics of Data Science (MoDS).”

Having received both his diploma and Ph.D. in mathematics from the University of Duisburg-Essen (Germany) in 2003 and 2005, Sebastian Pokutta was a postdoctoral researcher and visiting lecturer at MIT, worked for IBM ILOG, and Krall Demmel Baumgarten. Before joining ZIB and TU Berlin in 2019, he was the David M. McKenney Family Associate Professor in the School of Industrial and Systems Engineering and an Associate Director of the Machine Learning @ GT Center at the Georgia Institute of Technology as well as a Professor at the Universität Erlangen-Nürnberg. Among other accolades, Pokutta is a recipient of the prestigious NSF CAREER Award in 2015, which recognizes the work of faculty members who exemplify the role of teacher-scholars through outstanding research, excellent education, and the integration of teaching and research.

About the Gödel Prize

The Gödel Prize is an annual prize for outstanding papers in theoretical computer science. Named after Kurt Gödel in recognition of his significant contributions to mathematical logic and of his interest in what has become the famous “P versus NP” question. The Prize is sponsored by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery (ACM) Special Interest Group on Algorithms and Computation Theory (SIGACT) and includes an award of USD 5,000.

LINKS

• Sebastian Pokutta’s Personal Homepage
• The Gödel Prize
• Announcement of the 2023 Gödel Prize Winners and Papers