The 2023 Gödel Prize is awarded to the following papers:

• 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)
• Thomas Rothvoss: The matching polytope has exponential extension complexity. STOC 2014: 263-272. J. ACM, 64(6),1-19 (2017)

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.

Building on these techniques, Rothvoss showed that even for the perfect matching problem, which is polynomially time solvable, any extended formulation of its polytope must have exponential size. This shows that Edmonds’s characterization of the matching polytope from the 1960s is essentially optimal.

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)
Luca Trevisan (Bocconi University)