Abstract

Combinatorial problems like Traveling Salesman (TSP) optimize a linear function over some polytope P. If we can obtain P as a projection from a larger-dimensional polytope with a small number of facets, then we get a small linear program for the optimization problem; if we obtain P as a projection from a small spectrahedron, then we get a small semidefinite program. The area of extension complexity studies the minimum sizes of such LPs and SDPs. In the 1980s Yannakakis was the first to do this, motivated by flawed claims that one can efficiently solve TSP via a small LP. He proved exponential lower bounds on the size of symmetric LPs for the polytopes corresponding to TSP and to the matching problem. In 2012, Fiorini, Massar, Pokutta, Tiwary, and de Wolf proved exponential lower bounds on the size of all, also non-symmetric, LPs for TSP. The proof connects convex geometry with communication complexity, combinatorics, and even quantum computing. This result was followed by many new results for LPs and SDPs, for exact optimization as well as for approximation. This talk will describe the context and proof of the Fiorini et al. result, and briefly survey follow-up work.

Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf. In Journal of the ACM, Volume 62, Issue 2,  Pages 1-23, 2015 (earlier version in Proceedings of STOC'12). https://arxiv.org/abs/1111.0837

This paper shared the 2023 Gödel Prize.