On 23 June 2022, CWI researcher Ronald de Wolf and his co-authors received the prestigious ACM STOC 10-year Test of Time Award during the ACM Symposium on Theory of Computing (STOC), one of the most important conferences in theoretical computer science. Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf were given the award for their article ‘Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds’, originally published at STOC 2012. One of its main conclusions was that a particular attempt to solve the famous travelling salesman problem cannot possibly work.
Ronald de Wolf says about the article: “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, this 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, De Wolf and the rest of the team already received a Best Paper Award for their work.
Exceptional impact
The STOC Test of Time Award recognizes papers with exceptional long-term impact published in the ‘Proceedings of the Annual ACM Symposium on Theory of Computing’. The other winner of the 2022 award was Craig Gentry (STOC 2009) for his paper ‘Fully homomorphic encryption using ideal lattices’. Other winners of these awards include Cynthia Dwork, Manuel Blum, Dan Spielman, Avi Wigderson, David Chaum and Ivan Damgård.
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.
Slide at STOC ’22 with the names of the winners of the ACM STOC 10-year Test of Time Award.
More information
- The winning article: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. The journal version appeared as ‘Exponential Lower Bounds for Polytopes in Combinatorial Optimization‘ in the Journal of the ACM in 2015.
- Information on ACM STOC prizes
- News item from 2012 on this research article and the STOC 2012 Best paper Award: Decades-old P=NP ‘proof’ finally refuted
- News item (in Dutch) from Kennislink on the 2012 Best Paper Award for this work
- Contact data of Ronald de Wolf at CWI
- Personal homepage of Ronald de Wolf
- Algorithms and Complexity research group at CWI
- QuSoft
