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 winner of the 2023 Gödel Prize is 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 did his research in the Algorithms and Complexity group of CWI (Centrum Wiskunde & Informatica) in Amsterdam, the national research institute for mathematics and computer science in the Netherlands. He is also a part-time full professor at the ILLC of the University of Amsterdam and a member of QuSoft. In 2013 he received an ERC Consolidator Grant and in 2003 the Cor Baayen Award. His main scientific interests are quantum computing and complexity theory.
The award committee of the 2023 Gödel Prize consisted of Award Committee: Nikhil Bansal (University of Michigan), Irit Dinur (Weizmann Institute), Anca Muscholl (University of Bordeaux), Tim Roughgarden (Columbia University), Ronitt Rubinfeld, Chair (Massachusetts Institute of Technology) and Luca Trevisan (Bocconi University).
