University of Washington professor Thomas Rothvoss, a member of the Allen School’s Theory of Computation group with a joint appointment in the UW Department of Mathematics, has received the 2023 Gödel Prize recognizing outstanding papers in theoretical computer science for “The matching polytope has exponential extension complexity.” In the paper, Rothvoss proved that linear programming — a core technique in combinatorial optimization for modeling a large class of problems that are polynomial-time solvable — cannot be used to solve the perfect matching problem in polynomial time. He originally presented these results at the 46th Association for Computing Machinery Symposium on Theory of Computing (STOC 2014).
Rothvoss shares this year’s accolade with researchers Samuel Fiorini and Serge Massar of the Université Libre de Bruxelles, Hans Raj Tiwary of Charles University in Prague, Sebastian Pokutta of the Zuse Institute Berlin and Technische Universität Berlin, and Ronald de Wolf of the Centrum Wiskunde & Informatica and the University of Amsterdam. Two years before Rothvoss published his seminal result, that team proved the extension complexity of the polytope for the Traveling Salesperson Problem is exponential — confirming that there is no polynomial-sized extended formulation, and therefore no small linear program, that can be used to solve the TSP.
That result provided a partial, yet definitive, answer to a problem posed by theoretician Mihalis Yannakakis two decades prior. For Rothvoss and his colleagues in the tight-knit theory community, it was a watershed moment.
“Most of the time in complexity theory, we deal in conjectures but can’t actually prove any of them,” Rothvoss said. “On a good day, we can maybe prove that one conjecture implies another. So it was rather surprising when Sam and the rest of that group proved, completely unconditionally, the exponential extension complexity of the TSP polytope.”
The group further proved that its result extended to the maximum cut and stable-set polytopes, as well. But that proof, significant as it was, only answered the question for problems that are NP-hard. Inspired by the progress Fiorini and his collaborators had made, Rothvoss aimed to settle Yannakakis’ question once and for all when it comes to linear programs applied to polytopes that are not NP-hard — that is, well-understood polytopes, such as that of the perfect matching problem, for which polynomial-time algorithms for optimizing linear functions are known to exist.
And settle it, he did.
“I focused on it full-time for half a year,” Rothvoss recalled. “A couple of the technical aspects of that 2012 paper were also useful for my purposes, such as a technique drawn from Razborov’s classic paper on communication complexity, while others I had to modify.
“In particular, we knew the so-called rectangle covering lower bound used by Fiorini et al. to great effect in the case of TSP would not suffice for the matching polytope,” he continued. “In fact, the rectangle cover number for matchings is polynomial in the number of vertices, so it turned out that a more general technique — hyperplane separation lower bound — works instead.”
In the process of arriving at his proof, Rothvoss confirmed that Edmonds’ characterization of the matching polytope, made nearly half a century earlier, is essentially optimal. According to Allen School professor James R. Lee, his colleague’s work was — and remains — a significant insight with ramifications in mathematics, algorithm design and operations research.
“Thomas’ work is a masterful combination of ideas from two seemingly disparate areas of TCS,” said Lee. “It’s the synthesis of really profound insights of Yannakakis and Razborov from three decades ago, weaving together polyhedral combinatorics and communication complexity to settle a problem that essentially predates the era of P vs. NP.”
Rothvoss previously received the Delbert Ray Fulkerson Prize from the Mathematical Optimization Society and the American Mathematical Society for the same work. He is also the past recipient of a Packard Fellowship, a Sloan Research Fellowship, a National Science Foundation CAREER Award and Best Paper Awards at STOC, the Symposium on Discrete Algorithms (SODA) organized by the ACM and the Society for Industrial and Applied Mathematics (SIAM), and the Conference on Integer Programming and Combinatorial Optimization (IPCO).
The Gödel Prize, named for mathematical logician Kurt Gödel, is co-sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the European Association for Theoretical Computer Science (EATCS). Rothvoss and his fellow honorees will be formally recognized at STOC 2023 in Orlando, Florida next month. Learn more about the Gödel Prize here.