ACM prize and some thoughts on the Godel Prize

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 Neuman. 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 it in a given year.

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 Wolpert 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?

Computational Complexity published first on Computational Complexity