The 2023 Gödel Prize awarded to Ronald de Wolf et al.

The 2023 Gödel Prize is awarded to the paper by 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).

Linear Programming and polyhedral methods form the backbone of combinatorial optimization. Associating a polytope to a discrete optimization problem, and characterizing its structure, has long furnished important insights in combinatorics and algorithm design. A basic question is whether the polytopes for classical problems such as traveling salesman and matching admit a small description. Resolving a long-standing question, Fiorini, Massar, Pokutta, Tiwary and de Wolf made ingenious use of techniques from communication complexity (following a framework pioneered by Yannakakis) to show that any extended formulation for the TSP polytope has exponential size.