Tuesday, March 03, 2009

Algorithms for All

Last week I visited Edinburgh. Nice new CS building in an ancient university.

On Tuesday before a lunch talk, someone mentioned a new article the day before in the Guardian, a British paper, about the glory of algorithms with some concern that the article had misled people into thinking algorithms came from mathematics (the article ends with "Mathematicians rule!"). To me any publicity is good publicity but the good faculty at Edinburgh felt CS needed defending. To set the matter straight they decided to write a letter to the Guardian. Things moved very quickly, especially for a British university, and the letter was written, signed by many faculty members and sent by the end of the day.

I mentioned the Guardian letter and the controversy briefly in my Wednesday post.

What happened next I learned from Suresh. The Edinburgh letter was published Friday along with another letter from the Operations Research Society claiming algorithms as their own.

So who owns algorithms? We all do. Roughly CS analyzes algorithms and OR applies algorithms to real-world problems, all often based on important mathematical ideas and theorems. Algorithmic ideas now permeate many other areas of study such as physics, biology and economics. Algorithms rule!

9 comments:

  1. 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.

    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?

    ReplyDelete
  2. Perhaps CS, statistics, and OR should not have branched off from the math department in the first place?

    Ah the young'uns with so little sense of history.

    CS, statistics and OR were kicked out of the math department by mathematicians who found them too impure areas of research.

    ReplyDelete
  3. Lance asserts:
    So who owns algorithms? We all do!

    Lance, that is a fine post! It expresses a modern truth that has multiple aspects.

    First (and to borrow a phrase from Terry Tao's blog), progress in algorithms flows both from the abstract to the concrete, and from the concrete to the abstract. Thus mathematicians, scientists, and engineers all are playing vital roles in a vibrant algorithm-centric ecosystem.

    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 and for useful information).

    No doubt, many readers of Computational Complexity will assert that progress in their particular area of specialization also 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.

    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.

    In combination, these three mechanisms ensure that our Golden Age of Algorithms will help catalyze (we all hope) a Golden Age of Enterprise. Good!

    ReplyDelete
  4. I heard that Madhu Sudan is joining Microsoft Research as a full time researcher. Is that right!?

    ReplyDelete
  5. So who owns algorithms?
    This question is akin to asking who owns the real numbers. No one does. However,
    consider the history of the real numbers. The real numbers were postulated in a vague sense by the Greek geometers,
    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.

    The analogy with algorithms is striking.
    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.

    ReplyDelete
  6. 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.

    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.

    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.

    ReplyDelete
  7. Anonymous asserts: Mainstream mathematicians typically don't see algorithms as interesting objects of study in and of themselves.

    Hmmm, taking the converse, this amounts to claiming that if mainstream mathematicians are interested in a topic, that topic is not algorithmic.

    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?

    The point is that Lance's original assertion---"algorithms belong to everyone"---was absolutely right.

    ReplyDelete
  8. 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.

    ReplyDelete
  9. Anonymous asserts: "The truth is that while algorithms "belongs" to everyone, it is mainly done by computer scientists and taught in CS departments."

    This claim perhaps has appeared in memos written by CS department chairs to university presidents ... but my impression is that it poorly describes the actual development of human understanding of algorithms.

    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).

    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.

    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.

    ReplyDelete