tag:blogger.com,1999:blog-3722233.post8196421798673766569..comments2023-12-04T17:39:30.766-06:00Comments on Computational Complexity: The Man who loved AlgorithmsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-91668165397596442122007-06-27T07:45:00.000-05:002007-06-27T07:45:00.000-05:00So is Kailath, I thought the title was a little mi...So 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...Daniel Rudoyhttps://www.blogger.com/profile/03132410299644500040noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28858406967976765332007-05-28T10:11:00.000-05:002007-05-28T10:11:00.000-05:00How can an article with the name `The man who love...How can an article with the name `The man who <I>loved</I> algorithms' be about Donald Knuth? (I believe he is still alive and well and loving algorithms.)rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18923199818065263052007-05-26T16:53:00.000-05:002007-05-26T16:53:00.000-05:00I know him! :PI guess it is better to be a little ...I know him! :P<BR/>I guess it is better to be a little more open when considering other fields and people from there.<BR/>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!<BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82993988596231078182007-05-26T12:45:00.000-05:002007-05-26T12:45:00.000-05:00A 2006 interview with Knuth not linked from the Wi...A 2006 interview with Knuth not linked from the Wikipedia entry: <A HREF="http://www.stanfordalumni.org/news/magazine/2006/mayjun/features/knuth.html" REL="nofollow">May/Janue 2006 Stanford Magazine</A>. <BR/><BR/>I can use Kailath's paper(s) comparing Bhattacharyya distance (aka. classical fidelity) and divergence measures in <A HREF="http://www.cse.buffalo.edu/~regan/chess/fidelity/" REL="nofollow">my chess anti-cheating work</A>, 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?KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90234964305543635652007-05-25T11:07:00.000-05:002007-05-25T11:07:00.000-05:00Have fixed link to wikipediaentry on Knuth.THANKS ...Have fixed link to wikipedia<BR/>entry on Knuth.<BR/>THANKS for the correction.<BR/><BR/>bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59556207330758897462007-05-25T10:23:00.000-05:002007-05-25T10:23:00.000-05:00Bill, the link for Don Knuth's wikipedia entry is ...Bill, the link for Don Knuth's wikipedia entry is broken.Anonymoushttps://www.blogger.com/profile/08122513285361130315noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41726569811696003522007-05-25T09:26:00.000-05:002007-05-25T09:26:00.000-05:00To answer the question posed in the original post,...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. <BR/><BR/>EE 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. <BR/><BR/>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.Michael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60639863391610228242007-05-25T04:24:00.000-05:002007-05-25T04:24:00.000-05:00What is the title of Knuth's books?1. The art of c...What is the title of Knuth's books?<BR/><BR/>1. The art of computing lower bounds? NO<BR/>2. The art of computing upper bounds? NO<BR/>3. The art of becoming an engineer? NO<BR/>4. The art of counting? NO<BR/>5. The art of computer programming? YES<BR/><BR/>"Computer programming"!!!!!<BR/><BR/>It seems that D. Knuth is not that good after all. <BR/>:-))))) <BR/><BR/>DennyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15949869717674886182007-05-25T03:45:00.000-05:002007-05-25T03:45:00.000-05:00Come on! Engineering? That's not computer scienc...Come on! Engineering? That's not computer science. Next thing you know, a Turing award will be award for <B>programming</B> work. Yuck.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34569616016561969652007-05-24T20:02:00.000-05:002007-05-24T20:02:00.000-05:00Hmm, so it seems that there are some people out th...<I>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.</I><BR/><BR/>The 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31182031051443771232007-05-24T18:22:00.000-05:002007-05-24T18:22:00.000-05:00Hmm, so it seems that there are some people out th...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. Moreover, some of them believe that the aforementioned research areas also "produce" algorithms, thus are part of the theoretical computer science.<BR/><BR/>Really strange :-)<BR/><BR/>DennyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46219500240849132452007-05-24T13:59:00.000-05:002007-05-24T13:59:00.000-05:00Does Muthu know him? If not, he doesn't even exist...Does Muthu know him? If not, he doesn't even exist.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18097003236405896592007-05-24T12:54:00.000-05:002007-05-24T12:54:00.000-05:00By Donald Knuth's own criterion, Kailath is indeed...By Donald Knuth's own criterion, Kailath is indeed an algorithmist.<BR/><BR/>@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.''}, }Anonymousnoreply@blogger.com