Skip to content

The 2016 Knuth Prize

February 2, 2016

A non-announcement announcement

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]

8 Comments leave one →
  1. February 3, 2016 4:45 am

    Gödel’s Lost Letter is very-very important for CS community, so I think RJLipton+KWRegan will win🙂

    • Pipster permalink
      February 3, 2016 8:52 am

      Pip (RIP)

    • rjlipton permalink*
      February 3, 2016 11:13 am


      Thanks for the comment…really very nice

      Ken + Dick

  2. February 3, 2016 3:10 pm

    Why do the professionals consider the attraction of amateurs to great math problems so bad? For instance, maybe my naive amateur papers are only crackpottery garbage, but my new definitions can perhaps change the whole TCS toward a wonderful time of revolutionary discoveries, if the experts take them seriously into account upon their studies… Who knows?

    Anyway, see some them at:

    • o0o permalink
      February 4, 2016 1:35 pm

      As a motivated amateur myself, who does spend time attempting to understand “outsider” mathematics, I am unable to follow your arguments. I have some suggestions for you:

      – Remove all complaints about the reception of your work. It should stand on its own, such complaints may fit for a blog post, but not a mathematical paper. Likewise remove pejorative or superlative language.
      – Reformulate your work using normal notation. Introduction of non-standard notation will inhibit your readers’ ability to follow your arguments. Rewriting the proofs with accepted notations will also help you clarify your own ideas. Do not redefine standard definitions, or seem to be doing so. Introduce new definitions and prove how they relate to established ones. Take the time to use LaTeX, do not use Word or similar software.
      – If the notions you have introduced to solve the ‘big’ problems are valid, they will likely be fruitfully considered on their own, without reference to the famous problem. If you can show these definitions are intrinsically interesting and publishable on their own, you will find easier acceptance if they do indeed imply solutions to the ‘big’ problems.

      You may have interesting ideas, but if no one can understand them due to language and presentation, they will not find acceptance. Please understand, these issues are not unique to you, I frequently find the same issues in amateur mathematics papers online, but they certainly inhibit the reading of your papers.

      • February 4, 2016 5:25 pm

        If I follow your [very wise] advices right now, then I shall give up my ongoing research on how the math experts consider those [very freak] “outsiders”…

  3. Kerry Liles permalink
    February 5, 2016 11:00 am

    At the outset, “non-annoucement” instead of “non-announcement” (two instances I believe). As sticklers for absolute accuracy and conciseness, I predict you would like to know this. Alas, spell chequer, where art thou? Keep up the brilliant work.

    • February 5, 2016 1:54 pm

      Thanks. They do go thru LaTeX “ispell -t foo.tex” but hitting “a” to accept formatting elements sometimes carries over to a real word, as evidently happened here.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s