Renowned mathematician and artificial intelligence researcher, Professor Sebastian Pokutta, along with his co-authors and colleagues, has been awarded the prestigious Gödel Prize 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 to the field.
The awarded paper revolutionizes our understanding of hard computational problems, particularly the notorious Travelling Salesman Problem (TSP). For decades, researchers have sought to create an efficient linear program to solve TSP. Successful execution of such an endeavor would have profound implications for algorithmic efficiency across numerous computational challenges. However, this paper, building upon Yannakakis' work from 1988, 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 the application of linear programming for these hard problems.
Professor Pokutta, currently the Vice President of the Zuse Institute Berlin (ZIB) and a Professor of Mathematics at TU Berlin, shares this honor with co-authors Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf, reflecting a collaborative effort that has made significant strides in the field of theoretical computer science as well as colleague Thomas Rothvoss for his work ruling out efficient linear programs for the matching polytope.
The Gödel Prize, named in honor of Kurt Gödel, is jointly sponsored by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT). The annual prize, which includes a $5000 award, recognizes seminal work in theoretical computer science.
Pokutta's research lies 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. The paper has previously been recognized with the STOC Test of Time award in 2022 for its exceptional long-term impact, and the STOC Best Paper award in 2012, marking its enduring impact and significant contribution to the field.
Among other accolades, Professor 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 education and research.
He, along with his esteemed co-authors, will officially receive the Gödel Prize at the 55th Annual ACM Symposium on the Theory of Computing in June.
---
About the Gödel Prize:
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science. Named after Kurt Gödel in recognition of his major contributions to mathematical logic, the award 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). The Prize includes an award of $5000 and is presented annually at alternating conferences.
