Test of Time
Time is the ultimate critic. What future generations think of us and our work ultimately determines our standing or lack of it— Stewart Stafford
Bobby Kleinberg just reached out to those of us who post from time to time. He wanted some help in announcing a new STOC Test of Time Award.
So today, Ken and I put this together.
Bobby said:
As with FOCS, three awards will be given: one for papers from approximately 10 years ago, one for approximately 20 years ago, and one for approximately 30 years ago. The selection committee for this year’s award will be Joe Halpern, Mihalis Yannakakis, and Salil Vadhan.
I would suggest that one of Bobby’s papers could fit this award:
Group-theoretic algorithms for matrix multiplication
Henry Cohn, Robert Kleinberg, Balazs Szegedy, Christopher Umans
Well, I can say that without being out of order here because that paper was in FOCS, not STOC.
Criteria
Go here for details on how to nominate. By the way: Another test of Time is that the nominations are due relatively soon—May 24. So if you wish to nominate some paper please act soon.
Ken notes that the first criterion could also be called Leadership, the second always comes with an element of Surprise, and the last two have aspects of Applicability and Practicality. Adding those to my terms makes a double acronym APPLAUSE.
Early Early Years
I have been around long enough to fit the a 30++ years category, and Ken almost ditto. Here are some opinions on the early days. Those papers with
are an absolute must include—I hope you agree.
1981:
Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement
Use.
1982:
Shafi Goldwasser, Silvio Micali
Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information
Area.
1983:
Miklós Ajtai, Janos Komlós, and Endre Szemerédi
An 
Use and Proof.
Larry Stockmeyer
The complexity of approximate counting
Use.
1984:
Les Valiant
A theory of the learnable
Area and Else.
Narendra Karmarkar
A new polynomial-time algorithm for linear programming
Use and Proof.
Of course, these are my own opinions (with concurrence from Ken) and do not reflect those of organizations we belong to.
Open Problems
Ken thinks that one way not to be asked here about my own papers is to mention one, so here goes:
Ravindran Kannan, Richard Lipton
The Orbit Problem is Decidable
Proof. Ken adds: Could also be Surprise because we not only showed decidable but in polynomial time. But the real test of time here may be whether (despite some technical limitations) it proves useful to the great recent interest in adjacent kinds of orbit problems in invariant and reachability theory.
1983 sorting looks genuinely important to complexity as $CC^1$ containing $CH$ can supercede 1981, render 1982 useless, supercede 1983 approximate counting and 1984 LP and I cannot comment on 1984 learning theory. Is sorting in Logspace uniform TC^0?
It would be nice on the nominations page if they put links to the Tables of Contents for STOC 2011, 2001, 1991…
Great suggestion, Ryan! I’ve updated the call for nominations page to include links to the tables of contents.
Great idea, Ryan! I’ve updated the nominations page to include those links.