tag:blogger.com,1999:blog-3722233.post7439497391206903984..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: Algorithms for AllLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-89457601249286506572009-03-04T08:14:00.000-06:002009-03-04T08:14:00.000-06:00Anonymous asserts: "The truth is that while algori...Anonymous asserts: <I>"The truth is that while algorithms "belongs" to everyone, it is mainly done by computer scientists and taught in CS departments."</I><BR/><BR/>This claim perhaps has appeared in memos written by CS department chairs to university presidents ... but my impression is that it poorly describes the <I>actual</I> development of human understanding of algorithms.<BR/><BR/>To quote a few aphorisms (from imperfect 6:00 am memory) "Mathematical progress often flows from the concrete to the abstract" (Tao), "A great deal more is known than has been proved" (Feynman), and "I have had my results for a long time, but I do not yet know how I am to arrive at them" (Gauss).<BR/><BR/>All of these aphorisms illustrate how exceedingly often advances in algorithms begin with empirical insights and practical applications that only later---often many decades later---are refined into formal proofs.<BR/><BR/>It is true that CS (and Applied Math) departments are an important venue for this distillation---and yet overall, progress in algorithms is a creative human activity that has an exceedingly wide domain.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12557998962927234752009-03-04T07:45:00.000-06:002009-03-04T07:45:00.000-06:00I think the point is that students are misled by t...I think the point is that students are misled by the popular press. A mathematically talented high school student is likely to be steered toward math rather than (T)CS, and this is only reinforced by articles suggesting that algorithms = mathematics. The truth is that while algorithms "belongs" to everyone, it is mainly done by computer scientists and taught in CS departments.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11617562060790314202009-03-04T07:22:00.000-06:002009-03-04T07:22:00.000-06:00Anonymous asserts: Mainstream mathematicians typic...Anonymous asserts: <I>Mainstream mathematicians typically don't see algorithms as interesting objects of study in and of themselves.</I><BR/><BR/>Hmmm, taking the converse, this amounts to claiming that if mainstream mathematicians are interested in a topic, that topic is not algorithmic.<BR/><BR/>Does this mean, for example, that the study elliptic curve cryptography is not algorithmic? That the study of invex functions is not algorithmic? That studying the geometry of ruled Kählerian state-space manifolds is not algorithmic?<BR/><BR/>The point is that Lance's original assertion---"algorithms belong to everyone"---was absolutely right.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54463647587642260992009-03-04T00:37:00.000-06:002009-03-04T00:37:00.000-06:00Just because algorithms (just like real and comple...<I>Just because algorithms (just like real and complex numbers) have found its use outside of mathematics, it is ridiculous for CS or OR or for that matter a dozen other fields to claim ownership of it.</I><BR/><BR/>Algorithms have not only found use in CS, but it is within CS that they have been systematically studied and understood. Topics like algorithm analysis, randomized algorithms, complexity theory, approximation algorithms, data structures, etc... are all about understanding the power and limitations of algorithms. And these topics are central to CS, not math, not OR. <BR/><BR/>Mainstream mathematicians typically don't see algorithms as interesting objects of study in of themselves. Computer scientists do, and it is for this reason that the topics listed above were created. I think it is in this sense that CS "owns" algorithms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32608394804189054972009-03-03T16:15:00.000-06:002009-03-03T16:15:00.000-06:00So who owns algorithms? This question is akin to a...<I>So who owns algorithms? </I><BR/>This question is akin to asking who owns the real numbers. No one does. However, <BR/>consider the history of the real numbers. The real numbers were postulated in a vague sense by the Greek geometers,<BR/>analyzed more carefully by the founders of calculus (such as Newton, Leibniz etc.), leading to its precise definition (Cauchy sequences or Dedekind cuts) and finally developing into an immensely fruitful area of research namely real analysis. Even though the fruits of all this benefits every engineering and scientific discipline (as well as not-so-scientific ones such as economics), no one can argue that the reals were given birth to, nurtured and brought to adulthood by mathematicians over the period of two thousand years.<BR/><BR/>The analogy with algorithms is striking.<BR/>Starting from Euclid, through Gauss, Hilbert, Tarksi, Turing, Post, Markov, Godel, von Neumann, Turing -- the development of algorithms from ancient to the modern times was inside the framework of mathematics. Just because algorithms (just like real and complex numbers) have found its use outside of mathematics, it is ridiculous for CS or OR or for that matter a dozen other fields to claim ownership of it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59031421191452629642009-03-03T15:53:00.000-06:002009-03-03T15:53:00.000-06:00I heard that Madhu Sudan is joining Microsoft Rese...I heard that Madhu Sudan is joining Microsoft Research as a full time researcher. Is that right!?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80469260923923497782009-03-03T15:22:00.000-06:002009-03-03T15:22:00.000-06:00Lance asserts: So who owns algorithms? We all do!L...Lance asserts: <BR/><I>So who owns algorithms? We all do!</I><BR/><BR/>Lance, that is a fine post! It expresses a modern truth that has multiple aspects.<BR/><BR/>First (and to borrow a phrase from Terry Tao's blog), progress in algorithms flows <I>both</I> from the abstract to the concrete, <I>and</I> from the concrete to the abstract. Thus mathematicians, scientists, and engineers all are playing vital roles in a vibrant algorithm-centric ecosystem.<BR/><BR/>Second, for several decades progress in algorithms has shown the same exponential growth in capability as progress in computational hardware. This progress has been especially marked in algorithms on quantum state-spaces (where the mathematical blending of information theory, algebra, and geometry provides fertile foundations for progress) and in algorithms for large-scale scientific informatics (where global-scale databases in biology and astronomy can be mined for mathematical ideas <I>and</I> for useful information). <BR/><BR/>No doubt, many readers of <I>Computational Complexity</I> will assert that progress in <I>their</I> particular area of specialization <I>also</I> has been spectacular in recent years ... in which assertion they are absolutely correct! Truly, we are all of us participating in a generalized Golden Era of Algorithms.<BR/><BR/>Third, in facing the global challenges of team-building and enterprise, no single tool---not even money and politics---is as important as a solid algorithmic and/or simulation-based understanding of the enterprise. As a result, modern enterprises almost universally begin with a detailed algorithmic and/or simulation-based roadmap. It is around these algorithm-based roadmaps that consensus forms, teams are organized, and investors are recruited.<BR/><BR/>In combination, these three mechanisms ensure that our Golden Age of Algorithms will help catalyze (we all hope) a Golden Age of Enterprise. Good!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9106662816900085982009-03-03T13:29:00.000-06:002009-03-03T13:29:00.000-06:00Perhaps CS, statistics, and OR should not have bra...<I>Perhaps CS, statistics, and OR should not have branched off from the math department in the first place?</I><BR/><BR/>Ah the young'uns with so little sense of history.<BR/><BR/>CS, statistics and OR were kicked out of the math department by mathematicians who found them too impure areas of research.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52768018554813054522009-03-03T11:32:00.000-06:002009-03-03T11:32:00.000-06:00I don't think the OR society is claiming algorithm...I don't think the OR society is claiming algorithms as their own. In response to the description of algorithms as "safely guarded mathematical recipes", the letter suggests that they are used openly everywhere in the real world by OR practitioners and perhaps not so safely guarded after all.<BR/><BR/>As to who owns algorithms, it should be clear by now that the original algorithms were developed by mathematicians. Where is the controversy? Are the CS people at Edinburgh afraid that future funding might be incorrectly channeled into the math department rather than their own? Perhaps CS, statistics, and OR (see Mathematics Genealogy Project's definition of mathematics) should not have branched off from the math department in the first place?Anonymousnoreply@blogger.com