Ronald de Wolf (CWI, UvA, QuSoft) en zijn co-auteurs ontvangen de prestigieuze Gödelprijs voor uitmuntende papers in de theoretische informatica. De Gödelprijs wordt gezamenlijk uitgereikt door de ACM Special Interest Group on Algorithms and Computation Theory (ACM SIGACT) en de European Association for Theoretical Computer Science (EATCS). De prijs zal worden overhandigd tijdens STOC 2023, een van de belangrijkste conferenties in de theoretische informatica, die van 20-23 juni 2023 in Orlando, Florida, plaatsvindt. Dit jaar zijn er twee winnende artikelen. De andere winnaar van de Gödelprijs 2023 is Thomas Rothvoss.
Ronald de Wolf zegt: "Ik ben vereerd om samen met mijn co-auteurs deze prijs te winnen en om vermeld te worden tussen de geweldige papers en fantastische onderzoekers die deze prijs eerder hebben ontvangen." Eerdere winnaars van de Gödelprijs zijn bijvoorbeeld bekende onderzoekers als Cynthia Dwork, Shafi Goldwasser, Johan Håstad, László Lovász, Peter Shor, Dan Spielman, Mario Szegedy en Avi Wigderson.
Handelsreizigersprobleem
Auteurs Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary en Ronald de Wolf kregen de prijs voor hun artikel 'Exponential Lower Bounds for Polytopes in Combinatorial Optimization’. Een van de belangrijkste conclusies was dat een bepaalde poging om het beroemde handelsreizigersprobleem op te lossen onmogelijk kan werken. Ronald de Wolf legt uit: “Dit artikel weerlegt een poging om moeilijke rekenkundige problemen zoals het handelsreizigersprobleem (het Travelling Salesman Problem, TSP) op te lossen. We weten hoe we zogenaamde lineaire programma's efficiënt kunnen oplossen, dus sinds de jaren tachtig proberen onderzoekers een klein lineair programma voor TSP op te schrijven. Als deze aanpak slaagt, zou dat grote gevolgen hebben voor efficiënte algoritmen. Ons artikel - dat het werk van Yannakakis uit 1988 generaliseert - heeft echter definitief aangetoond dat deze aanpak gedoemd is te mislukken, door te bewijzen dat elk lineair programma dat TSP beschrijft exponentieel groot moet zijn. Het bewijs combineert hoog-dimensionale meetkunde, combinatoriek en zelfs een verband met kwantumcommunicatietheorie.”
Tijdens STOC 2012 ontvingen Ronald de Wolf en de rest van het team al een Best Paper Award voor hun werk en in 2022 wonnen ze de ACM STOC 10-year Test of Time Award.
Ronald de Wolf deed zijn onderzoek in de Algorithms and Complexity groep van het CWI (Centrum Wiskunde & Informatica) in Amsterdam, het nationaal onderzoeksinstituut voor wiskunde en informatica in Nederland. Daarnaast is hij deeltijdhoogleraar aan het ILLC van de Universiteit van Amsterdam en maakt hij deel uit van QuSoft. In 2013 ontving hij een ERC Consolidator Grant en in 2003 de Cor Baayen Award. Zijn belangrijkste wetenschappelijke interesses zijn quantumcomputing en complexiteitstheorie.
De toekenningscommissie van de Gödelprijs 2023 bestond uit: Nikhil Bansal (Universiteit van Michigan), Irit Dinur (Weizmann Institute), Anca Muscholl (Universiteit van Bordeaux), Tim Roughgarden (Columbia University), Ronitt Rubinfeld, voorzitter (Massachusetts Institute of Technology) en Luca Trevisan (Bocconi University).
