The May 2007 issue of IEEE SPECTRUM has on its cover the sentence
The man who loved algorithms
I was thinking that it would be an article about
Donald Knuth (See also
Wikipedia entry)
It was not- it was about
Thomas Kailath(See also
Wikipedia entry.) who won the
IEEE spectrum medal of Honor for
exceptional developments of powerful algorithms in the fields of communications, computing, control and signal processing
I will defer to the IEEE and assume that he has indeed
done excellent work.
I had never heard of this person. Some of you may have since he does have
some COMP SCI publications; however, I suspect most of you have not.
If not, then do we have a narrow view of algorithms?
My view is narrower than most and is summed up by
a quote Michael Sipser said at a Workshop on
Circuit Complexity about 20 years ago:
Algorithms are sanity checks on lower bounds.
By Donald Knuth's own criterion, Kailath is indeed an algorithmist.
ReplyDelete@inBook{Knuth:95, author = {M. Petkov\v{s}ek and H. S. Wilf and D. Zeilberger}, title = {$A=B$}, publisher = {A.~K.~Peters, Ltd.}, year = 1996, note = {Forward by Donald Knuth: ``Science is what we understand well enough to explain to a computer. Art is everything else we do. [\ldots] Science advances whenever an Art becomes a Science. And the state of the Art advances too, because people always leap into new territory once they have understood more about the old.''}, }
Does Muthu know him? If not, he doesn't even exist.
ReplyDeleteHmm, so it seems that there are some people out there that believe that linear algebra, numerical analysis, etc DO belong to mathematics and computer science. Moreover, some of them believe that the aforementioned research areas also "produce" algorithms, thus are part of the theoretical computer science.
ReplyDeleteReally strange :-)
Denny
Hmm, so it seems that there are some people out there that believe that linear algebra, numerical analysis, etc DO belong to mathematics and computer science.
ReplyDeleteThe methods used in numerical analysis (numerical recipes?) certainly qualify as algorithms, though not DISCRETE algorithms (and therefore appropriate for STOC/FOCS but not SODA?) A few CS departments still cover numerical analysis though this is not the norm these days. However, Kailath doesn't fit this category that well either. Maybe the point is that his research is more algorithmic than that of other people in EE doing signal processing.
Come on! Engineering? That's not computer science. Next thing you know, a Turing award will be award for programming work. Yuck.
ReplyDeleteWhat is the title of Knuth's books?
ReplyDelete1. The art of computing lower bounds? NO
2. The art of computing upper bounds? NO
3. The art of becoming an engineer? NO
4. The art of counting? NO
5. The art of computer programming? YES
"Computer programming"!!!!!
It seems that D. Knuth is not that good after all.
:-)))))
Denny
To answer the question posed in the original post, "...do we have a narrow view of algorithms?", the answer is "yes", if by "we" you mean the overwhelming majority of the FOCS/STOC/SODA community.
ReplyDeleteEE in general, and information theory in particular, has a lot of algorithmic work in it. Their inputs are different (often modeled as continuous instead of discrete), their models are different, and their techniques are different. But they're definitely doing algorithms, and questioning whether someone who wins and IEEE award is really doing algorithms because "we" don't know their name just demonstrates "our" ignorance, and highlights what I see as a long-standing problem in our community.
By the way, information theory (at least) does algorithms even according to the "sanity checks on lower bounds" definition. In coding, this corresponds to finding upper bounds on the capacity (lower bounds arise from giving an algorithm/demonstrating a code, while upper bounds must hold for all possible codes). Upper bounds problems are, naturally, often quite challenging.
Bill, the link for Don Knuth's wikipedia entry is broken.
ReplyDeleteHave fixed link to wikipedia
ReplyDeleteentry on Knuth.
THANKS for the correction.
bill g.
A 2006 interview with Knuth not linked from the Wikipedia entry: May/Janue 2006 Stanford Magazine.
ReplyDeleteI can use Kailath's paper(s) comparing Bhattacharyya distance (aka. classical fidelity) and divergence measures in my chess anti-cheating work, whose goal is to be algorithmic. Actually, here's a philosophy-of-language question along lines of comments above: when do statistical METHODS become ALGORITHMS?
I know him! :P
ReplyDeleteI guess it is better to be a little more open when considering other fields and people from there.
They may not be interested in our specific problems, but it doesn't mean what they do is not important. More importantly, and most probably, what will remain in the next 200 years from what we are working now is just a glimpse!
I know your point was not exactly this, but I found here a good point to say something about this bad behavior among many computer scientists I've seen.
How can an article with the name `The man who loved algorithms' be about Donald Knuth? (I believe he is still alive and well and loving algorithms.)
ReplyDeleteSo is Kailath, I thought the title was a little misleading. Any student in signal processing will know Kailath for his work in linear systems theory. I've come across some of his work in reproducing kernel hilbert spaces...
ReplyDelete