Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
IMHO the most prestigious prize in theoretical CS is the Nevanlinna prize. Not the Turing award.
Any prize with an age restriction foregoes its claim to "most prestigious" title and yes Virginia, that includes the Fields medal.The most prestigious prize in CS is undoubtedly the Turing Award (in spite of a certain recent controversial decision) and the most prestigious math award will soon be the Abel prize, with the Fields becoming a sort of "outstanding mathematical prodigy award" due to its age limitations.
What's this controversy?Please tell (or link)...
Unbelievable that Les Valiant hasn't won it as yet...
What's this controversy?Last year's award was given to Peter Naur for something that he himself claims not to have invented.
"the most prestigious math award will soon be the Abel prize"Not really. The Abel prize has so far focused on giving a large sum of money to people who did something good decades ago and are now inactive . It is thus both useless, since it does not give money to someone who can use it for further research, and utterly boring. But the prize could become relevant if the prize committee changes is current behaviour.
The Abel prize has so far focused on giving a large sum of money to people who did something good decades ago and are now inactive . This might have more to do with a "quick get'em before they die" attitude rather than a "lets wait until they are retired" focus as you claim.
"IMHO the most prestigious prize in theoretical CS is the Nevanlinna prize. Not the Turing award."Sure. Turing award is more prestigious.
It is thus both useless, since it does not give money to someone who can use it for further research, and utterly boring.I don't know about that -- not every award is (or should be) given with the expectation of additional results in the future. It's perfectly reasonable to give awards "merely" for extraordinary results in the past -- this may not spur continued productivity by the recipient, but the award itself can be something for younger researchers to aspire toward. Isn't that part of why such things are considered prestigious in the first place, that is, that they're recognizing a life of confirmed outstanding achievement (rather than the expectation of future success)?
Awards are nice for motivating the ambitious, but strong (okay, not-terrible) funding and good rapport with our non-TCS peers would do a lot more for the long-term prospects of complexity theory than having the right mix of prizes for junior/midlevel/senior researchers.
Awards are nice for motivating the ambitious, but strong (okay, not-terrible) funding and good rapport with our non-TCS peers would do a lot more for the long-term prospects of complexity theory than having the right mix of prizes for junior/midlevel/senior researchers.One of the theories is that awards generate publicity about excellence and in turn that sense of excellence helps to generate funding.
A few of the turing awards have been really sub standard. I guess, if there are no suitable nominations, its better not to give any award at all than to give it to undeserving people.
A few of the turing awards have been really sub standard.Yeah, this Frances Allen person doesn't have a single FOCS/STOC publication.
Yeah, this Frances Allen person doesn't have a single FOCS/STOC publication. (I understand that you were sarcastic..) but this just confirms my point that for theoretical computer science (by which I'm mainly referring to Complexity Theorey), the Turing award is not the most prestigious prize. Notwithstanding, I completely agree that the age restriction of the Nevanlinna prize does harm its prestige.
A few of the turing awards have been really sub standard. Looking at the list we need to remove the first 15 years or so when the pool to choose from was much smaller. The record until then is spotty. However, since 1980 all but one of the award winners seem fully deserving of the recognition. The one mistake can be explained by a faulty attribution from Knuth that somehow became universally accepted, namely BNF.for theoretical computer science (by which I'm mainly referring to Complexity Theorey) the Turing award is not the most prestigious prize.This is a cockamamie, starting from the fact that it equates TCS with complexity theory. I guess this means Jon Kleinberg and Bob Tarjan have to give their Nevanlinnas back.
I don't know who this one person is who keeps saying the Nevanlinna prize is more prestigious, but I sense that they are somewhat aghast that non-theoreticians sometimes win the Turing award (believe it or not, not all of the great contributions to CS come from TCS).With that being said, it seems fairly clear that most people feel like this year's Turing award is a bit baffling. Even non-TCS people have no idea who Fran Allen is (as somebody on Slashdot noticed, her wikipedia page was only created 2 weeks ago by a user with no other edits).
(I understand that you were sarcastic..) but this just confirms my point that for theoretical computer science (by which I'm mainly referring to Complexity Theorey), the Turing award is not the most prestigious prize. Wait, let me break this rediculously faulty-logic claim into pieces: (I) Turing award is given to non-theory people. Therefore, (II) the Turing award is not the most prestigious prize in TCS.The logic in this claim is hopeless. You could argue in the same way that the Nobel prize in economics is sometimes won by non-economisc people, and therefore it is not the most prestigious prize in Economics.Or that logs of wood always drown, and witches are not always made of wood, and therefore witches do not drown. (see also here )
The Turing award is not the most prestigious award in TCS because it is not an award in TCS but an award in CS. There - does that clear it up for everybody?
That logic would imply that the Turing award is not an award in Systems, or AI, or in Programming langauges or Numerical Computation (because not all winners fall in one cateqory).Lo and Behold, we just proved that the Turing Award is not Computer Science prize at all!
Giving Kleinberg the Nevanlinna prize certainly hurts its prestige. His undoubtedly great work is, nonetheless, a very poor example of the mathematical and theoretical depth of our field, which is what Nevalinna is supposedly given for. It's always a shame when a prize becomes a popularity contest.
Giving Kleinberg the Nevanlinna prize certainly hurts its prestige. I totally agree. We in the TCS community cannot afford to be seen hanging around people whose work is novel and relevant. I also agree about the goals of the prize which, from the web site, are stated to be "for outstanding contributions in Mathematical Aspects of Information Sciences". It should be clear to all that this is simply code speak for "mathematical and theoretical depth" as measured in number of greek symbols, integral signs, and new complexity classes defined per page. I sure hope that for the sake of the purity of TCS Jon does the right thing and gives the award back.
I will not speak on whether Nevalina should be about mathematical depth or not. Maybe it is strategic to just give it to new cool research.However, "mathematical depth" is for sure not about the number of integral signs or greek symbols. And it is certainly not about defining as many new complexity classes as possible.We have examples of long standing open problems which were solved (or partially solved) by the development of new and powerful mathematical understanding. That matches my intuitive understanding of depth much closer than defining many new problems and solving some of them.
Kleinberg's research is certainly timely, cool, appealing and so on. But actually wouldn't it have been nicer to give the award for solutions to old open problems, which maybe happen to also have practical impact, and also contain ideas that are interesting to a large audience with mathematical background. Surely, such examples must exist.
To Anon #22: 1) Anon #21 was being facetious. 2) According to your measure of "years since problem was posed" the theory of relativity is a minor contribution, since many of the questions were posed and answered by Einstein at the same time. Age might be a sufficient condition for difficulty (which shouldn't be confused with relevance) but it surely isn't a necessary condition for relevance, depth or significance.
Clearly the Nevanlinna prize should only be given for those who prove the most useless results in TCS. I mean, anything else simply lacks the mathematical and theoretical depth that one would expect for such a prestigious prize.
It's not clear on which side #25's comment is intended to be, but in case, let me point out that most of Kleinberg's research is by definitions "useless". It's in the realm of pure science where we're trying to get some understanding of a naturally occuring structure, and nobody claims we will get anything except some satisfying understanding.In fact, my own opinion is that CS was meant to be useful and we should give the prize to "deep" and useful mathematical contributions. Useful means profound algorithmic ideas which make it into practice. About practice is different from having an impact in practice; most of CS theory is not descriptive, and we should keep it that way.
A few "substandard" awards :1. Feigenbaum and Reddy...what did they do?Kleinberg's Nevanlinna a much better choice would have been Arora, Ran Raz, Agrawal...Most importantly, Turing Award is also becoming about women equality, liberation and all that crap. This is a gret disrespect to the likes of Yao, Gray, Hoare, Pnueli, Codd, Blum, Knuth...It is interesting to note that the chairman of the turing award committe was an equally unknown person. I don't know how much of an influence did he have though...
Wait, let me break this rediculously faulty-logic claim into pieces: (I) Turing award is given to non-theory people. Therefore, (II) the Turing award is not the most prestigious prize in TCS.You missed the point! My claim is not a logical one, rather an empirical one:Complexity Theory has milieu, community, trends, some problems that are generally recognized (by the community itself) as important and so forth.In this milieu, I claimed that for what I understand, the Nevanlinna prize is recognized as more prestigious (by which I mean a prize that puts the highest `tag of quality ' on the scientific products of the award winner).Personally, I have no bias here against the Turing award. On the contrary, I totally agree that it is faulty to have age restrictions on prizes awarded for scientists. I was just stating what I understand is an empirical fact, nothing more.
Anon #27 wrote: It is interesting to note that the chairman of the Turing award committee was an equally unknown person. I don't know how much of an influence did he have though...Does anybody know who was in the Turing award committee?
Ruzena Bajcsy was the chairwoman of the Turing award committeehttp://www.hpcwire.com/hpc/1278972.html
I think those people who have issues with Jon, they also say the same thing about Madhu Sudan compared with Arora.
To Anon 27: You strike me as a complete ignoramus and a highly immature person. Just because you are unaware of or do not like the contributions of certain people does not mean that they have not done great things.I am fully confident that you have neither produced nor are capable of work as produced by Kleinberg, Reddy or Feigenbaum.
Even non-TCS people have no idea who Fran Allen is (as somebody on Slashdot noticed, her wikipedia page was only created 2 weeks ago by a user with no other edits). I think this statement is quite possibly the most ridiculous thing posted on this blog. One's worth as a researcher is determined by how old their wikipedia entry is? I might add that neither Sanjeev Arora nor Omer Reingold have Wikipedia entries.
Wikipedia has a huge webpage for Stewie Griffin.'nuff said.
I think the prize to Jon Kleinberg is well deserved. And so will be the other suggestions such as Sanjiv Arora.The richness and variety of scientists we have form a partial order with many maximal elements. It is perfectly fine for the prize committee to have different taste than yours or mine. Often it is a hard decision for a prize committee to pick a winner.I do not know the work of Frances Allen but by the citation of the prize it looks like she has done great work and well deserved the prize. Of course if you or I were in the prize committee then we may have chosen a different winner. For sure we would also have hard time choosing the winner. It is very likely the winner we would have chosen must also have been seriously considered by this prize committee.In TCS or Math like any other Science, our goal is to simplify our understanding (for simplicity of this sentence, assume that things we do not understand are infinitely complicated:)) So mathematics which is simple is a plus and not a minus. Simple mathematics is a sign of deep thinking. Every theorem takes a creative idea. Some ideas are so creative that the accompanied proof looks simple! We can't hold it against the scientist.Personally, among the ideas which look simple to me varies from the theory of relativity in physics to the capital markets in economics. Both have profound effect! What "technical" mathematics we need after the idea is super important but not as much as the original ideas.Sure it is okay to disagree with the committee. In our hearts we could always consider another deserving non-winner with the highest regards. But we should realize that we ourselves need to earn the community's highest trust to have our opinion reflected in the official collective opinion.
The committee's opinion shouldn't be glorified as the "official collective opinion". People get appointed to prize committees for two reasons (having done outstanding research or being politically adept), neither of which is well correlated with the wisdom and perspective needed to select one winner from the entire field. Basically, most prizes involve an arbitrary choice from a sensible short list, and there's nothing sacred about that winner (who deserves little if any more respect than the others on the short list).Allen's work really doesn't seem to be widely known within the broad CS community, and there's surprisingly little information about it on the web (perhaps because much of it was long ago). Some people seem to be assuming that the committee made a poor choice, and that's certainly a possibility. However, it's important to keep in mind the other possibility: that Allen's important work has been marginalized within CS. (Perhaps because she is female, perhaps because she has no Ph.D., perhaps because she works in industry and publications have not been her top priority.) The mere fact that the committee selected Allen does not mean she was a good choice, but one can't assume she was a bad choice just because she wasn't already famous.
but one can't assume she was a bad choice just because she wasn't already famous.Or that she was a bad choice just because she's a woman, as many closet misogynists do, usually stating their objection in the cannonical form of "I'm not sexist/racist but [insert wildly sexist/racist remark here]".For the record old timers know who Fran Allen is. In her career she moved to the top of the academic hierarchy in IBM, which some might recall was one of the finest research organizations in the world. This Turing award is the fifth going to an active member of IBM research.It seems to me that those assuming a priori that she wasn't deserving are just looking for excuses for their misogynist opinions. If on the other hand some take the time to familiarize themselves with her record and contributions (as opposed to the age of her wikipedia entry) and still feel she's underserving I might still not agree with them but at least I would have some respect for their opinion.
Anonymous#36. I agree with you mostly. As you could see my second paragraph itself talks about that often there are many deserving candidates and it is quite subjective and hard to pick one over the other.The two skills you mentioned to pick a prize winners, i.e., doing good research himself/herself and political adeptness are exatly what are needed in making a good decision.Political adeptness is a skill involves earning trust from others. Picking a winner from several entirely different areas also requires political skills. One must be able to collate opinion from different areas. I do not think there is a single person who is expert in all the areas of computer science. One definitely needs political skills and trust from others to be able to pick a prize winners from a diverse set of areas.Sometimes the same skills are needed to pick a hidden gem. From the prize citation, I think Allen deserve the prize. Those who are objecting to it should first go and read her important pieces of work. May be that's what the prize committee did. And may be doing that will change the opinion of these folks. If not convinced even then, then write an informed and educated opinion.Regarding your (anonymous#36) comments which were in between the lines that she was in a minority (a woman from indsutry with no formal phd), there is some truth to it. There is some disadvantage to be in minority, but I do not think it is organized. I do not think most of us even pay any attention to the author, his/her gender, affiliation, or qualification, of the paper. Being in several PC, I have seen papers from many big shots gets rejected with equal criticism as a paper from a newbie. (Though these big shots do not lose heart and take the feedback in the right spirit and submit the paper to the next conference, where the paper is often accepted.)I agree that there is a discrimination against simple proofs. I have seen a nice theorem with a simple proof gets rejected but the same, sometimes even strictly weaker theorem, with a very complicated proof gets accepted. A complicated proof to a simple theorem sometimes is a disservice. It takes away the enlightenment about the nature's deep reasons behind the theorem.We discriminate against simple proofs, because as one earlier poster observed, complexity of the proof, i.e., number of different greek symbol used is considered the sign of deep mathematics. Unfortunately that poster is not alone. There are several of us who think this way.Most ideas worth pursuing are typically those which are simple and self explanatory. Which brings a feeling, I should have thought about it first. This feeling means, even though I did not think the idea first, but I recognize it and can work with it.
--- 1. Feigenbaum and Reddy...what did they do? Ed Feigenbaum co-developed the first expert system, Dendral.
Thinking of prizes as pointing out human reference models, it is relatively unimportant who agrees that the recipient is the best; but the aim should be that most people accepts him/her as a good, inspiring model. As a theoretical computer scientist, my reference comes mostly, rather, from the Gödel prize. By the way, among the 60+ people having obtained so far a Fields or a Nevanlinna (or the newly stablished Gauss), I could not spot a single woman.J L Balcázar
Well said J L Balcázar.
Once again, those who comment on this blog (and perhaps the TCS community in general, in which I count myself a member) put their myopia, narrow-mindedness, bitterness and irrelevancy on open display. No need to even reference previous posts; just read back over it yourselves.