Tuesday, June 3, 2008

Best of?

Today was the third time in a couple of months when I was asked to make a "most super of the superstars" list for TCS. I never had anything close to a good answer, so let's hear it from the readers of this blog :)

Please nominate people for the following 2 categories:

  1. "best" 5 TCS researchers ever;
  2. "best" 5 TCS researchers based on work from the past 15 years only.
If this is not obvious, the purpose of the best-of list is not to give these people some praise. I'm sure they couldn't care less about how much some anonymous commenters on my blog like them :)

It's also not to say that brilliant work in TCS is concentrated in the papers of these 5 guys. Some of the best results ever came from people with just 1 or 2 nice results in their entire career, and presumably these people will not be on the best-of list.

The purpose of these nominations is to see what we tend to appreciate in TCS these days, when it comes to appreciating researchers instead of results. From the questions I'm getting, it seems junior people need a few role models while struggling to get started, and it would be nice to let them pick an idol or two :)

This is one of the few posts where I would appreciate anonymous responses, but please think seriously about your nominations (top 5 makes for a nontrivial threshold).


Anonymous said...

I'm curious...in what contexts were you asked these questions?!

Mihai said...

On the one hand, by people in the field who are doing some soul-searching, and asking "what exactly do we appreciate in a researcher these days?" ... I think it would be interesting to have a mini-sample of answers to see what people appreciate.

On the ohter hand, by people on the edges of the field (either too young, or in some adjacent field), who want to look for some inspiration when starting to work more seriously in TCS. Math is very careful to provide iconic role models, and they spend a lot of time writing about the quirky personalities of their demigods. I think TCS may be missing some of that.. (Well, I don't think we want to push it like Math does, but a small dose might help some junior people.)

Luca Aceto said...


I agree that role models are important for young researchers. I trust that interviews with some of the giants in TCS and pieces explaining their scientific development, their opinions and the origin of their seminal contributions would be avidly read by the new generations of TCS researchers.

Off the top of my head, I can name three examples close to my research areas:

Martin Berger. An Interview with Robin Milner, which I published in an ENTCS volume at some point.

Moshe Vardi Speaks Out (on the Proof, the Whole Proof, and Nothing But the Proof) by Marianne Winslett. SIGMOD RECORD, Volume 35, Number 1, March 2006.

G.D. Plotkin. The Origins of Structural Operational Semantics, where Plotkin describes how structural operational semantics came about.

I am sure that more such examples are out there, and I hope that others will point them out. Still I think that we can do more to offer role models to the researchers who will be the future of TCS.

BTW, I assume that your view of TCS encompasses the topics covered by the two-volume Handbook of TCS and more.

Mihai said...

Thank you for the links, Luca!

But I must admit, I was aiming for nominations closer to my part of TCS (algorithms/complexity), because that's what a reasonable person would ask me about.

rgrig said...

Perhaps popularizing peoples archive among your peers will help. At the moment Knuth is there.

Anonymous said...

Geometry votes for Bernard Chazelle (for list 1?) and Timothy Chan (for list 2?).

Aaron said...
This comment has been removed by the author.
Anonymous said...

hehe, interesting.

1. No offense to anyone. My suggested names are just for a gossip fun. If your name is not in the list, it may not be because your work is not good enough: it's quite likely due to my ignorance of of the field.

2. It is hard to perfectly distinguish between TCS and discrete math. Let's say... only those who have enough publications in typical TCS conferences/journals count. (So, sorry, Paul Erdős!)

3. Since we've kicked out Paul, let's also kick out Alan Turing by only aiming at work after 1970.

Not through a serious comparison, on top of my head are (in the alphabetical order of their last name):
Noga, László, Sasha, Bob, Leslie, Avi, Andy

Maybe I'm a bit biased towards complexity theorists?

Anonymous said...

How about last names for those of us "too young" to know all the names on your list? (I was missing Bob and Sasha.)

Anonymous said...

Didn't you miss out Richard Karp? :-)

Anonymous said...

I think it is foolish to ask for the "best five" in a partial order which has way more than five maximal elements.

There are so many parameters to be considered (productivity, relevance, opening of new fields, impact outside the field, influence within the field) that the best we can hope is for pareto maximal points.

To the ones you listed, one would have to add, off the top of my head:

Karp, Christos, Bernard, Ron, Adi, Cook, Manuel, Turing, Rabin, Mehlhorn, Micha...

I'm sure there are another dozen or so missing from the list.

Mihai said...

Anons, correct me if I'm wrong. I believe the people that were mentioned by first names are:

* Dick Karp
* Noga Alon
* László Lovász
* Sasha Razborov
* Bob Tarjan
* Leslie Valiant
* Avi Wigderson
* Andy Yao
* Christos Papadimitriou
* Bernard Chazelle
* Ron Rivest
* Adi Shamir
* Stephen Cook
* Manuel Blum
* Michael Rabin
* Kurt Mehlhorn
* Micha Sharir

Anonymous said...

Leo Guibas should be there also...

Anonymous said...

Let me make a case for Mike Paterson (linear unification, impossibility of distributed consensus, binary space partition trees, finding medians, string convolutions, overhang from SODA 06, etc). Work across logic, decidability, circuit complexity to algorithms, pure, and not only applicable, but already applied. :)

-- metoo