Sunday, January 20, 2019

ACM prize and some thoughts on the Godel Prize

(ADDED LATER: deadlines for some of these awards have passed but here are ones
coming up soon:

Godel Prize: Feb 15

Knuth Prize: Feb 15

SIGACT News Dist Service: March 1


As Lance Tweeted, and I will re-iterate, nominations for the following prizes
are due soon and you can nominate people here

Godel Prize for outstanding paper in TCS. (Godel mentioned P vs NP in a letter to Von Neumann. I've heard it said that its too bad they didn't work on it-- either it would be solved or we'd know its hard. Frankly, I think enough smart people have worked on it that we already know its hard.)

Knuth Prize for outstanding contributions to foundations of Computer Science. (its a greater honor to have a prize  named after you in your lifetime then to win a prize!)

Dijkstra Prize (I wonder if having `ijk' in his name inspired him to work in algorithms)

Kanellakis Theory and Practice Award.

Lawler Award for Humanitarian Contributions within CS and Informatics.

ACM Distinguished Service Award

Danny Lewin Best Student Paper Award (best student paper at STOC)

The Best Paper award (Best paper at STOC, Best paper at FOCS)

(The last two I doubt you can nominate someone for.)

A few thoughts on the Godel Prize:

1) You can win the Godel Prize twice and some people have: Goldwasser, Hastad, Arora, Szegedy, Spielman, Teng. Spielman-Teng have won it as a team twice.

2) GLAD there is no limit to how many can win. If a paper has a lot of people on it (and this has happened) then FINE, they're all winners! According to The Big Bang Theory (the TV show, not the theory) in Physics at most 3 can win a Nobel Prize in Physics for the same breakthrough in a given year. The show itself shows how stupid the policy is.

3) I either knew and forgot or never knew that DPDA Equiv is decidable! Glad to now it just in time for teaching Automata theory this spring.

4) Looking over the list reminded me that there are some papers in the intersection of those I want to read and those I am able to read! Though not many. Most I want to read but they seem hard.

5) The Kanellakis award is for theory that is PRACTICAL. Could someone win a Godel AND a Kannellakis award for the same paper (or set of papers). I found one sort-of case ( (a) below) and one definite case ( (b) below).

a) Moshe and Wolper won the 2000 Godel Prize for Temporal Logic and Finite Automata (I should also read that before my class starts)

Holtzmann, Kurshan, Vardi, and Wolpert won the 2005 Kanellakis prize for Formal Verification Tools.

I assume the two works are related.

b) Freund and Schapire won the 2003 Godel Prize and the 2004 Kanellakis Award, both for their work on boosting in Machine Learning.

6) Why is it the  Godel Prize and the Kanellakis Award? What is the diff between a prize and an award? A quick Google Search says that an Award is a token of effort and merit, while a Prize is something you win in a competition. I doubt that applies. I suspect they are called Prize and Award from historical accident. Does anyone know?


  1. What's up with the time limit? An entirely arbitrary rule, in my opinion. If we don't want the "classics" to double-dip, that can be enforced directly (e.g., if you won the Knuth or Turing prize, you can't be nominated for the same work).

  2. I assume you mean that for the Godel Prize, to quote
    ``The main results were not published (in either preliminary or
    final form) before Jan 1, 2006''
    They also have
    ``The paper was published in a recognized refereed journal before Dec 31, 2018''

    SO, why the first rule? Good question! Readers- please leave comments on why they have these rules and are they a good idea.

  3. Our friend von Neumann ends with two 'n's.
    Interestingly, there's no rule prescribing the ending in tersm of 'man' or 'mann'. Daniel A. Spielman has only one 'n'.

  4. "Wolpert" should actually be "Wolper". Pierre Wolper ( is one of the increasing number of examples of a computer scientist who claimed the ranks in his own university and is now the rector of the University of Liege.

    Here is a question you might want to consider in a future post: Do computer scientists make good rectors/presidents of universities?

  5. EG and Luca A- thanks for your corrections which I have made.

    EG- Indeed, spelling is not as logical as math. I tried to use that as an excuse for my bad spelling in grade school (I still spell badly but do not try to excuse it). My teachers didn't buy it.

    Luca A- I suspect that a study of what fields do well at what admin jobs (e.g., CS as rector) would be good to do, though if you prove no correlations, nothing learned? And there are enough admin-people to make a study stat sig (unlike looking at US persidents know math, as I blogged on

    The problem with such studies is that if you do the study and find no correlations-- do you know anything? I supposed you do but still disapointing.