- 1996: Andrew Yao
- 1997: Leslie Valiant
- 1999: Laszlo Lovasz
- 2000: Jeffrey Ullman
- 2002: Christos Papadimitriou
- 2003: Miklos Ajtai
- 2005: Mihalis Yannakakis
Tuesday, April 10, 2007
Knuth Prize goes to Nancy Lynch
The Knuth Prize for 2007 was announced: Nancy Lynch.
The formal announcement is here.
The Knuth Prize is awarded for a lifetime of work in the foundations of computer science. This is in contrast to
awards that are for one work (e.g., best paper at STOC). A best paper award can look silly 10 years later;
however, a lifetime-of-work award has much less chance of that.
The Knuth Prize is $5000 plus $1000 travel expenses to go pick it up. Do they make you fill out forms and give
them your receipts? This is a small amount of money as prize money goes.
The Knuth Prize is given out every 1.5 years, so saying that Nancy Lynch is the `2007 winner' isn't quite right.
Donald Knuth has never won the Knuth Prize, though he certainly should. Is he eligible?
Previous winners are below. Impressive bunch!
Subscribe to:
Post Comments (Atom)
who came up with the one every 1.5 years schedule? And just why on earth did they choose to do it that way?
ReplyDeleteThe prize is awarded every year and a half because it is a joint award between ACM-SIGACT, which sponsors STOC, and IEEE-TCMFC, which sponsors FOCS. This way it can be awarded alternately at STOC and FOCS. The other solution would have been to give out two every year, but that seemed too frequent for a lifetime achievement award.
ReplyDeleteHmph, does distributed computing really count as TCS?? Even this famous FLP result is not mathematically deep.
ReplyDeleteThere's a topic for your blog, Bill -- Mathematical Depth! Dear Anonymous 3: Mathematical depth means making connections no one ever made before, not producing a turgid proof. NP means easily verifiable. Feynmann used to say that if we couldn't explain concepts to advanced undergraduates, we didn't really understand them at all. Nancy L's book reads like a dream. Such exposition requires extremely advanced mathematical sophistication. Anybody can present something that's too hard to understand.
ReplyDelete"Mathematical depth means making connections no one ever made before"
ReplyDeleteThat's cute. But no, I'm sorry, it doesn't.
Distributed computing, or more precisely Concurrency Theory, has developed deep connections with abstract homotopy theory (in the sense of Quillen), and this is as deep you can get in contemporary mathematics. Having said this, I do not know if Nancy Lynch's work has anything to do with these developments, other than introducing some basic topological concepts to the area.
ReplyDeleteFLP is just a big nasty adversarial argument. It's nothing to do with topology. At least not by the time when it was published. But the truly original contribution of FLP is seeing distributed computing as state transitions, which is now as obvious as falling apples, or entropy of information. I guess the true meaning of a life-time award is not how deep the awardee's work is, but a nowaday common sense is first introduced by him/her.
ReplyDeleteIt seems a lot of people confuse "depth" for "mathematical sophistication". IMO, what should matter in our community is "computational depth", in the sense that we should value a result if it exposes or explains something that is either fundamental or has wide ranging implications in our understanding of computation.
ReplyDeleteI don't really care whether a theorem is proved using combinatorics, algebra or topology. What I care about is the result, and what it means about computation. If the mathematics used are "sophisticated" then great (especially if it means we can use new machinery), but I don't believe we should judge a result on this basis.
How come whenever an award is announced on this blog, there's always a ton of TCSers shit-talking about the awardee (e.g. Knuth Prize and Turing Award)? I don't think there is a whinier subfield in all of CS.
ReplyDeleteHow come whenever an award is announced on this blog, there's always a ton of TCSers shit-talking about the awardee
ReplyDeleteI totally agree with the previous comment. Those shit-talking people are thousands of years far from getting any of these awards. Maybe this explains why they can only say "this is not deep" or "that is not mathematical".
My "favorite" is when the award recipient shit-talks about the award committee.
ReplyDeleteI don't think there is a whinier subfield in all of CS.
ReplyDeleteAgain, the problem is that TCS, by which I am mainly referring to computational complexity theory, is by large part, a vivid subfield of mathematics. Applied CS, is a vivid part of engineering.
Therefore, this kind of negative debate is going to continue, as both fields have different goals, different tastes, different motivations, different techniques and so forth.
Whiners, the Knuth prize award "may also be partly based on educational accomplishments and contributions such as fundamental textbooks and high-quality students". Apart from Yao and Ajtai, all the other past recipients not only possess a "sustained record of high-impact, seminal contributions to the foundations of computer science", as required, but have published books that are real gems.
ReplyDeleteDistributed computing is, in many ways, one of the most successful instances of /theory of computing/ in the sense that it is first-rate theory that relates (and affects) computing.
ReplyDeleteIn that respect, this area shows the impact of Nancy Lynch in combining solid theoretical foundations, clever mathematics (yes...), and ramifications for real systems.
The other area that has similar achievements is database theory (and indeed, some of the past winners have been involved in database theory).
This area used to have good STOC/FOCS representation, but it was marginalized, and it is the loss of the TCS community.
Distributed computing is, in many ways, one of the most successful instances of /theory of computing/
ReplyDeleteThere is a problem here with the term theory.
In applied fields like CS, people tend to characterize the concept of "theory" as something that is lack of immediate applications.
This interpretation is wrong in my view.
For something to become a Theory, it has to develop deeper and abstract net of notions, assumptions, directions, views, explanations of certain phenomena, etc.
I can't see how Distributed Computing is a Theory in that sense; but maybe I'm not too familiar with it.
The FLP impossibility result was a big surprise to many people involved in building distributed systems, even those who were quite mathematically sophisticated. I recall attending a meeting in the late 1980's a year or two after the FLP paper had appeared, at which an excellent researcher, well known for work on distributed and parallel numerical algorithms, made consistency claims for an asynchronous algorithm that directly contradicted the FLP impossibility result. When he was challenged on this by those who knew the FLP result, he still could not believe it at the meeting and was not convinced until he was walked through the details of the proof in the days after the meeting.
ReplyDeleteTo anon 15:
ReplyDeleteThe goal of the TCS field is to both model computation and describe what types of things are and are not possible in those various models. So, by definition, modeling computation in a distributed setting and providing algorithms and impossibility results for computation in that model constitutes work in TCS.
deeper and abstract net of notions, assumptions, directions, views, explanations of certain phenomena
ReplyDeleteI cannot think of a better desciption for the best work in Distributed Computing.
The added bonus is that these certain phenomena are inherent in most computing systems of today.
I don't think there is a whinier subfield in all of CS.
ReplyDeleteClearly, you've never seen a full professor reduced to obscene gestures and foul language when you bring up an industrial lab that has gotten a lot of good press for alternative engineering solutions that ignore the work of him and his subfield.
So, by definition, modeling computation in a distributed setting and providing algorithms and impossibility results for computation in that model constitutes work in TCS.
ReplyDeleteTheoretical Computer-Science (TCS) is a composition of two pre-defined notions. So TCS is not a definition in itself, and certainly not a definition of some collective research directions and goals.
Of course, you can define a new term "TCS" to be anything you wish; Which I think is both senseless and is irrelevant to what I claimed before:
For something to becaome a theory it has to conform to some standards.
For instances, I know of two theories relating to algorithms:
1. Computability or recursive theory, characterizing in broad sense what can be computed in principle.
2. Computational Complexity Theory, characterizing what can and can't be computed by bounded resource computations.
I do not know of any other general Theory of Algorithms. Hence, I do not regard Algorithmics as pertaining to the theory of computer-science, though it is standard to regard it as a part of TCS.
Previous comments claimed that distributed computing does indeed constitute a theory. I am not familiar with this field, and so I will take their word for it.
Hence, I do not regard Algorithmics as pertaining to the theory of computer-science, though it is standard to regard it as a part of TCS.
ReplyDeleteThis is the theory as equivalent to computational complexity view, which is often derived from notions of theory-as-equivalent-to useleness-in-practice which come from mathematics.
However, to understand TCS one needs to look at physics not mathematics. Theoretical physics is defined as developments relevant to physics which are done on paper with mathematical tools and rigor. This stands in contrast to non-theoretical physics developments which take place in the lab.
Under this definition, logic, algorithms, machine learning, computational complexity, computabiliti theory, quantum algorithms, and approximation and parameterized algorithms among others areas fall squarely within the purview of TCS.
"For instances, I know of two theories relating to algorithms:
ReplyDelete1. Computability or recursive theory, characterizing in broad sense what can be computed in principle.
2. Computational Complexity Theory, characterizing what can and can't be computed by bounded resource computations."
I said it once, and I'll say it again. Just as with computational complexity theory (which you say does constitute theory), considering any other model of computation then characterizing what can and cannot be done in *that* model should also constitute theory. Models for distributed computing are only one such example.
Furthermore, algorithmics and complexity are heavily intertwined, so to say one constitutes theory while the other doesn't seems strange. One end result of coming up with an algorithm is further understanding of the extent of your computational ability in whatever model your algorithm works in. How does this not fall under "characterizing what can and can't be computed by bounded resource computations", i.e. computational complexity theory?
google "How to start your Ph.D. study", you will find some comments Yuanyuan Zhou made regarding the CS programs at Berkeley, Yale and Illinois. Very interesting.
ReplyDeleteIs there any translation of that "How to start your Ph.D. study" to English?
ReplyDeletePLEASE HELP
ReplyDeleteA little out of Context but I didnt know what to do...
I have Developed an Polynomial algorithm for Graph Isomorphism and also coded it.The Conjecture is that G.I. is in P.
Now,I DESPERATELY NEED some Difficult cases of NON-ISOMORPHIC GRAPHS for testing the Algorithm that fail the current softwares and algorithms like NAUTY.
Also its my Masters Thesis and I am on a deadline..(just 3 weeks)
Can someone PLEASE PLEASE tell / help me with such Cases..
I already tried contacting Researchers but havent got any reply..
PLEASE PLEASE help me with such difficult NON-ISOMORPHIC Graphs that are Difficult to Detect ASAP..
Waiting for a response :
bharaj.tarandeep@gmail.com