Two Other Tests of Time

Mihalis Yannakakis 70-Fest and the 2023 Gödel Prize

2020 AAAS election—congrats on that too

Mihalis Yannakakis is being honored with a 70th-birthday festival next month at Columbia University in Manhattan. It is organized by Xi Chen, Ilias Diakonikolas, Kousha Etessami, Christos Papadimitriou, Dimitris Paparas, and Rocco Servedio.

Today we congratulate him and consider this as one way to mark a “test of time.” Then we discuss another.

There is a free but required registration for the August 16–18 event. Here is the current all-star list of speakers and topics:

Our friend Vijay Vazirani leads off with a talk that will reference Mihalis’s ideas on linear programming and optimization problems. The fourth talk by Toniann Pitassi is on communication complexity. These lead us to think of a variation on the “test of time” idea.

We have just been discussing ACM STOC and IEEE FOCS “Test of Time” awards. We posted a note in 2021 when they were created, and sure enough, Mihalis was one of three judges on the initial panel.

A Second-Order Test of Time

The above awards are “first-order” in the sense of being direct honors for a paper. The papers are expected to have stimulated other important papers, which might later receive their own awards. Our idea for a second kind of test-of-time award inverts the time flow.

A prize for a paper that unambiguously led to papers that won prizes, without having won a prize itself.

Here is the paper—note it is singly authored:

• M. Yannakakis, “Expressing Combinatorial Optimization Problems by Linear Programs,” ACM STOC 1988 and J.C.S.S. special issue, 1991.

And here are the papers it led to—winning the 2023 Gödel Prize no less:

• Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf, “Exponential Lower Bounds for Polytopes in Combinatorial Optimization, ACM STOC 2012 (with different title) and Journal of the ACM 2015.

• Thomas Rothvoss, “The matching polytope has exponential extension complexity, ACM STOC 2014 and Journal of the ACM 2017.

The former paper also won the 2022 Test of Time 10-year award; the latter will be up for the first time next year. But Michalis’s paper did not win in 2022 when it was eligible for the 30-year award with its four-year horizon rule; two other papers from the 1988 STOC did win. Nor does the paper seem to be mentioned or specifically implied in the citation for Mihalis’s 2005 Knuth Prize. Thus it seems to meet the eligibility condition for our prize.

The relevance condition is clear: The 2023 Gödel prize citation says that the five authors of the first paper

“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.”

The second paper is cited as “Building on these techniques, …” The Test of Time citation notes that the first paper “resolved a 25-year open problem”—namely one that was posed by Yannakakis as they say in their abstract. In our own post on this topic in 2012 we called Michalis’s 1988 work “a famous paper.” Yet, again, it seems to be eligible for our no-prizes prize.

Open Problems

Is Michalis’s 1988 paper really eligible for our prize, or has it already won a prize we haven’t found?

Again, we congratulate Mihalis warmly on his 70th birthday and we congratulate the winners of the 2023 Gödel Prize.