Allan Borodin

Allan Bertram Borodin is a University of Toronto professor whose research is in computational complexity theory and algorithms. He has co-authored papers with some of the best researchers in computer science including his longtime friend and colleague Turing Award winner Stephen Cook. 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 published papers in algebraic computations, resource tradeoffs, routing in interconnection networks, parallel algorithms, online algorithms, adversarial queuing theory and information retrieval. As of November 2011, Borodin is still active in teaching at approximately 70 years of age and has no plans to retire.

He 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. He 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. In 2008 Borodin won the CRM-Fields Prize.

See also

• Gap theorem
• Online algorithms
• Computational Complexity

References

• Allan Borodin (1972). "Computational complexity and the existence of complexity gaps". Journal of the ACM 19 (1): 158–174. doi:10.1145/321679.321691. 

External links

• Allan Borodin at the Mathematics Genealogy Project.
• Home Page at University of Toronto
• ALLAN BORODIN: RECIPIENT OF THE 2008 CRM-FIELDS-PIMS PRIZE