First of all, appologies for the last post. I managed to explain the purpose of the game very badly. It generated a long list of names of very common suspects, which of course contained zero information.
Now let's try to fix it. Please nominate your favorite theory researcher, together with a 3-line description of the reasons for your nomination. I imagine a comma-separated list of results would work very well, as would more complex explanations.
With this ammendment, maybe we can answer the original questions of (1) understanding how we appreciate researchers these days -- actually state a short explanation for why we value these people; (2) having a somewhat meaningful narrative for the junior people who might ask such a question -- a list of names without any justification is not so inspiring, since they haven't been exposed to our mob's peculiar mentality.
Also, here are the rules to keep this interesting and decent:
- only post anonymously;
- feel free to ask for clarifications on somebody else's nomination. What the heck, post rebuttals if you like;
- understand that this is just a summer game for a bit of fun and a bit of understanding the community we live in (I think it would be enlightening to see what our peers value);
- focus on the goal is to understand what we value, and ignore the impact that your nomination (or rebuttal?) might have on a specific person. Of course all these people are too senior to care whether some anonymous commenters on my blog like them or not :) You don't need to make them happy, and there no way you're realistically going to insult one of them...
- don't complain that there's no way to compare so many uncomparable people. I am hoping we're all old enough to understand the impossibility of such a pure comparison. Be subjective! That's what we want to understand -- out community's subjective thinking.
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
14 comments:
Since you want rebutals =) why is Sasha Razborov on a top 5 list? Not to say he shouldn't be, but I don't understand why people put him for.
I know Sasha and if a word from someone like me maters, he is a very very smart person. But he only wrote 3 publications that us mortals can understand a bit: natural proofs, monotone circuits, and set disjointness.
I guess monotone circuits was dead end so it shouldn't also count... Many people can make up suggestions for attacking a big problem, and the suggestions may look well for few years, but if they don't work well after, there is no credit to receive, no?
Are we giving lots of credit for just trying? I guess that is also fine.
A., your question raises a very related one: how many "really great" results do we remember from say 15 years ago? It depends on your subjective measure of really great, but what's a reasonable number? I would guess pure complexity theorists would remember about 15, and pure algorithmists would remember about 50 :)
So maybe you are applying an algorithms standard to a complexity person :)
Mihai: you start and name 5 ;-)
A: Then you should give your list so that we can compare :)
Anon, if somebody is asking a question, then almost by definition he is not senior enough to have a claim at the top 5, so your comment is useless. There's no point to jump at the neck of a guy who wonders about something, even if you disagree with the question. Just answer it if it's obvious.
Anon, if somebody is asking a question, then almost by definition he is not senior enough to have a claim at the top 5, so your comment is useless. There's no point to jump at the neck of a guy who wonders about something, even if you disagree with the question. Just answer it if it's obvious.
Why are you so insecure all the time?
Well, I'll start with an under-hyped person, not mentioned during the last post.
Mike Fredman for:
* FKS dictionaries. Concept: worst-case queries are possible for hash tables, even if updates are randomized. Impact: used everywhere; set the standard for follow-up work in dictionaries (dynamic, deterministic, succinct, ...)
* Fibonacci heaps. Concept: decrease key can be faster in priority queues.
* the first cell-probe lower bounds for dynamic data structures. Concept: you should study the cell probe model! Impact: solved some key problems; led to a very active area of research, in which the original techniques remain central.
* fusion trees and atomic heaps. Concept: can search in o(lg n) using multiplication and bit operations. Impact: intense study of searching and sorting in the word RAM.
* pairing heaps. Concept: self adjusting priority queues for decrease key. Impact: it is still a big open problem to understand them; Fredman himself made major progress in 1998, disproving a 12-yo conjecture in a tour-de-force paper.
* all-pairs shortest-paths in subcubic time. Concept: we can solve it in O(n^2.5) comparisons, "nonconstructively." Impact: major open problem today to get a uniform algorithm with running time O(n^(3-eps)).
* the X+Y problem. Concept: can sort X+Y in O(n^2) comparisons. Impact: major open problem to get o(n^2 * lg n) uniformly. Defining the X+Y problem crystalized many gaps in computational geometry (we don't know whether some O(n^2 * lg n) algorithms can be improved)
(Sorry, I wrote more than I should to combat the underhyping phenomenon... Future nominations will probably be shorter.)
I am defending an anonymous guy from a meaningless attack by another anonymous guy, and now I'm "so insecure all the time"??
Since I am doomed to never understand this sort of comments, can we stick to TCS please?
I'm amazed no one has suggested Shafi Goldwasser (winner of two Godel prizes).
Maybe we need to define out terms better. Are we looking for top people still active today? Or top people by their best contribution? Or top people by integrating over their career contributions?
I'm sure there are another dozen or so missing from the list.
Shafi and Mike Fredman are certainly two of the dozen or so which I said were missing from the list.
I would certainly also propose Miklós Ajtai, for:
* the AKS sorting network, solving a problem considered central at the time, by using technical ideas far ahead of their time.
* his part in the AC0 lower bounds (independent discovery, as far as I understand).
* the first serious lower bound in the cell-probe model. The problem studied (predecessor search) and the technique (an incipient form of round elimination) have been central in more recent research.
* the seminal paper on the proof complexity of the pigeon-hole principle.
And two very big hits from the past decade:
* lattice-based cryptography.
* the first superlinear lower bound for boolean branching programs.
Anon, to be honest, I was hoping for a more interesting discussion about younger people (say, judging only results from the past 15 years). Fredman, Shafi, and almost everybody else who was mentioned, are in the established canon. If a few of them are forgotten, it's just oversight.
Their nomination gives us little information about what we value these days. We know those people are important, and therefore whatever the heck they did must've been important. If we want to learn something about our current thinking, we should look more at young people where we can actually make a fresh judgment, as opposed to repeating what other people told us.
Ok, so let me throw out one:
Ken Clarkson, for
* almost singlehandedly reviving computational geometry by throwing randomization into the mix: specifically his work on random sampling in computational geometry, which is one of the more powerful techniques in use today.
* His work on iterative reweighting as a technique for solving covering problems in geometry.
* His early work in nearest neighbors in metric spaces.
I will join in with a nomination for Mike Paterson:
linear unification, impossibility of distributed consensus, string matching and convolution, median with limited memory, binary space partition trees, selection, and the recent soda 06 on overhang...
Work spans algorithms, complexity and decidability.
-- metoo
Post a Comment