Allan B. Borodin

Department of Computer Science

University of Toronto

Research

Professor Borodin has had a long and distinguished research career in the mathematical foundations of computer science. He has had a huge impact on the field, making a wide variety of contributions with important connections to computer science in general. His central area of interest, computational complexity, addresses the basic issue of determining the minimum resources required to solve computational problems. In particular, he has made fundamental contributions to algebraic computations, resource tradeoffs, routing in computer networks, parallel algorithms, and online algorithms. He also initiated the field of adversarial queuing theory. Other areas of Professor Borodin’s research that has wide-ranging impact include parallel computation and packet routing, adversarial queuing theory, and mathematical aspects of information retrieval.

Teaching

Professor Borodin has made tremendous contributions to Canadian university education, designing novel courses in computational complexity theory, algebraic complexity, online algorithms, approximation algorithms, and randomized algorithms. He designed and taught (six times) a first-year undergraduate seminar course on “Great Ideas in Computing”. This course has exposed students without a computer/technical background to many of the ideas and concepts that have made computing pervasive. He has also recently designed a 2nd year Computer Science course “Social and Economic Networks Models and Applications” which attracted students across the university, including social sciences, economics and computer science.

Graduate Supervision

He has graduated 29 MSc students, and his 16 completed PhD students have gone on to successful careers at major universities and in industry, and two of them, Ian Munro and David Kirkpatrick, recently joined Borodin as Fellows of the Royal Society of Canada. Service and Leadership. Borodin joined the recently formed Computer Science Department in 1969, and was heavily involved in the growth of the department as it became one of the top ten departments in North America. He served as Department Chair from 1980 to 1985 and later he was called upon to serve as the Acting Chair in 1992-93 during a crisis concerning the health of the Chair at that time. Since then he has played a senior advisory role in the department, as well as chairing many important departmental committees. One of Borodin’s most recent roles involved creating (with Greg Wilson) a highly innovative Professional Masters program (the MScAC program) that welcomed its first students in Fall ’10.

Recognition

Borodin has been appointed University Professor in 2011. He is Fellow of AAAS (2012), Fellow of the Fields Institute (2008) and Fellow of the Canadian Royal Society (1991) and holds the 2008 CRM-Fields-PIMS Prize.