Professor Allan Borodin

In 1963, Professor Borodin completed his undergraduate BSC degree in mathematics at Rutgers University. Following his undergraduate work, he became a “Member of Technical Staff'' at Bell Laboratories in New Jersey where he was involved in the development of computer controlled electronic switching systems while earning a part-time MSC at Stevens Institute of Technology. In 1966, he returned to full time graduate studies in the new Computer Science program at Cornell University, becoming the first graduate of the program.

After receiving a PhD from Cornell, Professor Borodin joined the recently-formed Computer Science Department at the University of Toronto in 1969.  He 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 1992-93. Recently, he co-chaired the committee responsible for designing and implementing a new professional masters program and remains actively involved in all aspects of this program during its first year of operation. He was also an active member of the committee responsible for the recent redesign of the undergraduate curriculum. He has been an editor for many journals and was managing editor of the SIAM Journal of Computing, helping to make it a premier journal for theoretical computer science.

Professor Borodin has been a Fellow of the Royal Society of Canada since 1991 and a Fellow of the Fields Institute since 2008. He has been a Lady Davis visiting professor at the Hebrew University and the Technion, Varan visiting professor at the Weizmann Institute, and has also held visiting appointments at IBM Research, Cornell, ETH Zurich,
Université de Nice, MIT, Università di Roma, and the Institute for Advanced Studies.
He was the recipient of the 2008 CRM-Fields-PIMS Prize, the premier prize for mathematical research awarded jointly by the three Canadian mathematics institutes.

Professor Borodin has a long and distinguished research career in theoretical computer science.  His central area of interest, computational complexity and algorithm design, addresses the basic issue of determining the minimum resources required to solve computational problems.  A common theme in Borodin's research is that he explores fundamental questions that seemingly should be well understood but often defy answers to even the most basic aspects of these questions.  Hence, he has often been at the forefront of developing new models and problem formulations that have become standard frameworks for computer science studies.

Professor Borodin's research has impacted a wide variety of areas including algebraic complexity, network routing, parallel computation, information retrieval, algorithmic mechanism design, resource tradeoffs, online computation, and adversarial queuing theory. His early work on algebraic complexity led to surprisingly fast new algorithms for solving a large number of problems, and culminated in the textbook ``Computational Complexity of Algebraic and Numeric Problems'' which served as the most important reference in the field for 25 years. He was a pioneer in work relating fundamental resource measures in complexity theory, and proved a landmark result establishing the minimum time-space product required for sorting.  In the mid 1980's he turned his attention to the nascent field of online algorithms, and was instrumental in introducing the now standard notion of metrical task system and establishing the importance of competitive analysis as a benchmark performance measure.  His work culminated in the 1998 textbook “Online Computation and Competitive Analysis'' which remains the standard in the field.  Later he applied the adversarial perspective of competitive analysis to queuing theory, and became the driving force in establishing the new field of adversarial queuing theory. Currently he is working on defining and analyzing precise models for basic algorithmic techniques, and has shown how to prove surprisingly strong limitations on these techniques for solving a large variety of problems. His other current research interests include information retrieval, algorithmic game theory and algorithmic aspects of social networks.