Faculty II - Mathematics and Natural Sciences

News

All news

Prof. Dr. Sebastian Pokutta receives Gödel Prize

Prof. Dr. Sebastian Pokutta, head of the "Mathematical Optimization" group at the Institute of Mathematics and member of the Cluster of Excellence MATH+, and his co-authors were awarded the prestigious Gödel Prize at the end of June 2023 in recognition of their influential work in combinatorial optimization [1].

In their award-winning work, Fiorini, Massar, Pokutta, Tiwary, and de Wolf solve a 20-year-old problem and make a seminal contribution to combinatorial optimization. They proved that any linear program describing the infamous Travelling Salesman Problem must be exponentially large. In doing so, they established a final frontier for the application of linear programming to this type of complex computational problem. 

The results were obtained by a new connection that the authors made between one-way quantum communication protocols and semidefinite programming reformulations of linear programs.


[1] Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf: Exponential Lower Bounds for Polytopes in Combinatorial Optimization. STOC 2012: 95-106. J. ACM, 62(2), 17:1-17:23 (2015).

The Gödel Prize is an annual award for outstanding work in theoretical computer science. Benannt ist er nach Kurt Gödel in Anerkennung seiner bedeutenden Beiträge zur mathematischen Logik und seines Interesses an der berühmten "P versus NP"-Frage. The award is sponsored by the European Association for Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computation Theory (SIGACT) of the Association for Computing Machinery (ACM) and carries a $5,000 prize.

More information:

 

© Beate Rogler / MATH+