SCIENTIFIC PROGRAMS AND ACTIVITIES

Centre de recherches mathematiques,
Fields Institute,
Pacific Institute for the Mathematical Sciences

CRM-Fields-PIMS Prize Lecture
Monday April 28, 2008-- 3:30 pm
at the Fields Institute

The CRM-Fields-PIMS prize is intended to be the premier mathematics prize in Canada. The winner receive a monetary award, and an invitation to present a lecture at each institute during the semester when the award is announced. The prize recognizes exceptional achievement in the mathematical sciences.

Allan Borodin
University of Toronto

Understanding Simple Algorithms: Toward a More Systematic Study of Algorithms

Richard Karp has called Computer Science the systematic study of algorithms. This raises 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. 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''. But while there has been a rich and ongoing development of new and often
surprising algorithms in diverse areas, I would argue that conceptually simple algorithms are often used for expediency and sometimes even to obtain the best known results for many fundamental problems. An ambitious (or perhaps naive) goal is to develop a theory for ``simple algorithms'', starting off with greedy or myopic 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.

Professor Borodin is a world leader in the mathematical foundations of computer science. His influence on theoretical computer science has been enormous, and its scope very broad. Jon Kleinberg, winner of the 2006 Nevanlinna Prize, writes of Borodin, "he is one of the few researchers for whom one can cite examples of impact on nearly every area of theory, and his work is characterized by a profound taste in choice of problems, and deep connections with broader issues in computer science." Allan Borodin has made fundamental contributions to many areas, including algebraic computations, resource tradeoffs, routing in interconnection networks, parallel algorithms, online algorithms, and adversarial queuing theory.

Professor Borodin received his B.A. in Mathematics from Rutgers University in 1963, his M.S. in Electrical Engineering & Computer Science in 1966 from Stevens Institute of Technology, and his Ph.D. in Computer Science from Cornell University in 1969. He was a systems programmer at Bell Laboratories in New Jersey from 1963-1966, and a Research Fellow at Cornell from 1966-1969. Since 1969 he has taught with the computer science department at the University of Toronto, becoming a full professor in 1977, and chair of the department from 1980-1985. Professor Borodin has been the editor of many journals including the SIAM Journal of Computing, Algorithmica, the Journal of Computer Algebra, the Journal of Computational Complexity, and the Journal of Applicable Algebra in Engineering, Communication and Computing. He has held positions on, or been active in, dozens of committees and organizations, both inside and outside the University, and has held several visiting professorships internationally. In 1991 Borodin was elected a Fellow of the Royal Society of Canada.

An article with further information on Professor Borodin's work can be viewed here.

Previous recipients of the prize are H.S.M. (Donald) Coxeter, George A. Elliott, James Arthur, Robert V. Moody, Stephen A. Cook, Israel Michael Sigal, William T. Tutte, John B. Friedlander, John McKay, Edwin Perkins, Donald A. Dawson, David Boyd, Nicole Tomczak-Jaegermann and Joel Feldman.

Established in 1994, the CRM-Fields Prize recognizes exceptional research in the mathematical sciences. In 2005, PIMS became an equal partner in the prize, and the name was changed to the CRM-Fields-PIMS Prize. A committee appointed by the three institutes chooses the recipient.

To learn more about the prize, please visit www.fields.utoronto.ca/programs/scientific/crm-fields-pims/

Back to top