Ronald de Wolf from CWI and his co-authors receive the 2023 Gödel Prize for outstanding papers in theoretical computer science.
Ronald de Wolf (CWI, UvA, QuSoft) and his co-authors receive the prestigious Gödel Prize for outstanding papers in theoretical computer science. The Gödel Prize is jointly awarded by the ACM Special Interest Group on Algorithms and Computation Theory (ACM SIGACT) and the European Association for Theoretical Computer Science (EATCS). The prize will be awarded during STOC 2023, one of the most important conferences in theoretical computer science, which takes place on 20-23 June 2023 in Orlando, Florida. This year, there are two winning articles. The other paper receiving the 2023 Gödel Prize is by Thomas Rothvoss.
Ronald de Wolf says: “I am very proud and humbled to win this prize along with my co-authors, and to be listed among the amazing papers and amazing researchers that have received this prize before”. Earlier winners of the Gödel Prize include well-known researchers like Cynthia Dwork, Shafi Goldwasser, Johan Håstad, László Lovász, Peter Shor, Dan Spielman, Mario Szegedy and Avi Wigderson.
Travelling Salesman Problem
Authors Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf were given the award for their article ‘Exponential Lower Bounds for Polytopes in Combinatorial Optimization’. One of its main conclusions was that a particular attempt to solve the famous travelling salesman problem cannot possibly work. Ronald de Wolf explains: “This paper refutes an attempt to solve hard computational problems such as Travelling Salesman (TSP). We know how to solve so-called linear programs efficiently, so since the 1980s researchers have been trying to write down a small linear program for TSP. If successful, this approach would have momentous consequences for efficient algorithms. However, our paper - which generalizes work by Yannakakis from 1988 - definitively showed that the approach is doomed to fail, by proving that every linear program that describes TSP needs to be exponentially large. The proof combines geometry, combinatorics, and even a connection with quantum communication theory.”
At STOC 2012, Ronald de Wolf and the rest of the team already received a Best Paper Award for their work, and in 2022 they won the ACM STOC 10-year Test of Time Award. Ronald de Wolf won the ERCIM Cor Baayen Award in 2003.
https://www.cwi.nl/en/news/goedel-prize-for-ronald-de-wolf/
https://www.sigact.org/prizes/gödel.html
