The 2016 Knuth Prize

Crop from Farkas Prize src

Michel Goemans is the chair of this year’s ACM/IEEE Knuth Prize committee. He teaches at MIT and among many wonderful achievements co-won the 2000 MOS/AMS Fulkerson Prize with David Williamson for their great work on approximation for MAX CUT and MAX SAT and other optimization problems.

A few days ago he emailed me to ask if Ken and I would announce this year’s call for nominations.

Of course, as Michel wrote in his email to me, he realizes that we really do not usually make announcements. And indeed he is correct. So Ken and I are confronted with a dilemma. We want to help, but our main purpose at GLL is to present time-independent posts that balance history and technical details. Besides, if we start doing announcements like this, then year-over-year it would become like Groundhog Day. Our problem is:

How do we make the announcement and still follow our usual form?

A second potential problem is that if we were to start doing announcements like this, then year-over-year it could become like “Groundhog Day.” So we ask, “How do we make the announcement and still follow our usual form?” Besides…

Prizes I

One idea we had was that we would look at the history of prizes. Prizes in science and math have been around for many many years. There are two types of prizes; well there are many types, but there are two extremes. One is called ex ante prizes and the other is called ex post prizes. An ex ante prize is an attempt to use money to direct research. They are of the form:

If you can solve X, then you will win the following amount of money.

An early example was the Longitude Prize, which was based on the reality that knowledge of latitude is easy to refresh by looking at the sun and stars, but using them for longitude requires accurately knowing the local time.

In 1714, the British government offered a very large amount of money for determining a ship’s longitude. The top prize was 20 thousand British pounds—an immense amount of money at the time. John Harrison was awarded the top prize in 1773, which he solved by creating a clock—amazingly compact like a watch—that kept accurate time even on a ship at sea. It did this in calm seas, rough seas, hot temperatures, or cold temperatures. A great read about the prize, its solution, and the controversy in paying Harrison is Longitude: The True Story of a Lone Genius Who Solved the Greatest Scientific Problem of His Time, by Dava Sobel.

A math example of an ex ante prize was the Wolfskehl Prize. Paul Wolfskehl created the prize named for him for the first to present a valid proof of Fermat’s Last Theorem. Of course, Andrew Wiles won the prize in 1997.

Some have stated that such prizes are not very useful. They often increase visibility of the problem, but attract amateurs who may or may not really understand the problem. The more recent Clay Prizes are ex ante, and it is unclear if they had any effect at all on the solution of the first of the prize problems to be solved: the Poincaré Problem. Recall the solver, Grigori Perelman, refused the prize money of $1,000,000.

Prizes II

Nobel Prizes are ex post prizes as are our own Turing Awards—okay they are called “awards” but that is a minor point. The Knuth Prize is definitely an ex post prize. It is given for not one achievement, but rather for a lifetime of work in the area of theory of computing. The call states:

The Prize is awarded for major research accomplishments and contributions to the foundations of computer science over an extended period of time.

I did win the prize two years ago, in 2014. I was thrilled, honored, and surprised. There are so many great theorists that I was very honored to receive it. Clearly, now is the time to try and put together a strong case for your favorite colleague. Only one can win, but you cannot win if there is not a serious case put together. So good luck to all. The committee consists of Allan Borodin, Uri Feige, Michel Goemans, Johan Håstad, Satish Rao, and Shang-Hua Teng. Here is the information on making a nomination. Nominations are due on Mar 31, 2016.

Laci Babai won it last year. Of course this was for his past work and its great innovations and deep executions, including a share of the first ever Gödel Prize. But we may have to credit the 2015 committee with prescience given Laci’s achievement with Graph Isomorphism (GI). Likewise, planning for a Schloss Dagstuhl workshop on GI began in 2014 without knowing how felicitous the December 13–18, 2015 dates would be. Perhaps there is a stimulating effect that almost amounts to a third category of prizes—as per a tongue-in-cheek time-inverting post we wrote a year ago.

Open Problems

Who will win this year? Of course the winner has to be nominated first—unless it’s the MVP of the NHL All-Star Game. There are many terrific candidates and I am glad not to be on the committee that has to decide. One prediction is that whoever wins will be extremely elated and honored.

[spellfix in subtitle]