Allan Borodin

(Université de Toronto)

Prix 2008 CRM-Fields-PIMS Prize

Why Simple Algorithms Can Be Complex

Richard Karp has called Computer Science the systematic study of algorithms. This begs the question as to how much the design and analysis of algorithms is a systematic study or science as opposed to say an art form as suggested by the title of Don Knuth's influential texts. To be sure, the foundation for the science exists in the form of the well-accepted Church-Turing thesis which formulates a precise mathematical model for what constitutes an "algorithm'' and hence what is "computable''. While there has been a rich development of new and often surprising algorithms in diverse areas, I would argue that the current best known algorithms for many fundamental problems are derived using conceptually simple algorithms (although the actual algorithms and analysis need not always be so simple). My ambitious (or perhaps naive) goal for several years has been to develop a theory for "simple algorithms'', starting off with "greedy or greedy-like algorithms''. I will review some of the history of previous efforts in this regard, some recent ideas and results, and my current thinking about the power and (provable) limitations of simple algorithmic paradigms. In particular, I will present the priority algorithm framework as a model for greedy-like optimization algorithms, and then discuss how this framework can be extended to model some common forms of simple dynamic programming, backtracking and primal dual algorithms.

Le vendredi 28 mars 2008 / Friday, March 28, 2008
16 h 00 / 4:00 p.m.

Centre de recherches mathématiques
Université de Montréal
avillon André-Aisenstadt, 2920, ch. de la Tour
Salle / Room 6214


Une réception suivra la conférence au Salon Maurice-l'Abbé,
Pavillon André-Aisenstadt (Salle 6245).

A reception will follow the lecture in Salon Maurice-l'Abbé,
Pavillon André-Aisenstadt (Room 6245).