Allan Borodin

Allan Borodin
Born	1941 (age 83–84)
Alma mater	Rutgers University Stevens Institute of Technology Cornell University
Awards	ACM Fellow (2014) Order of Canada (2020) [1]
Scientific career
Fields	Theoretical computer science
Institutions	University of Toronto
Thesis	Computational Complexity and the Existence of Complexity Gaps  (1969)
Doctoral advisor	Juris Hartmanis
Website	www.cs.toronto.edu/~bor/

Allan Bertram Borodin CM (born 1941) is a Canadian-American computer scientist who is a professor at the University of Toronto. ^{[2] [3]}

Biography

Borodin did his undergraduate studies at Rutgers University, earning a bachelor's degree in mathematics in 1963. After earning a master's degree at the Stevens Institute of Technology in 1966 (while at the same time working part time as a programmer at Bell Laboratories), he continued his graduate studies at Cornell University, completing a doctorate in 1969 under the supervision of Juris Hartmanis. He joined the Toronto faculty in 1969 and was promoted to full professor in 1977. He served as department chair from 1980 to 1985, and became University Professor in 2011. ^{[2] [3] [4]}

Awards and honors

Borodin was elected as a member of the Royal Society of Canada in 1991. In 2008 he won the CRM-Fields-PIMS prize. ^{[3] [5]} He became a fellow of the American Association for the Advancement of Science in 2011, ^[6] and a fellow of the Association for Computing Machinery in 2014 "For contributions to theoretical computer science in complexity, on-line algorithms, resource tradeoffs, and models of algorithmic paradigms." ^[7] In 2020 he received the Order of Canada. ^[1]

Selected publications

Research articles

• Borodin, Allan (1972). "Computational complexity and the existence of complexity gaps". Journal of the ACM . 19 (1): 158–174. CiteSeerX   10.1.1.453.2374 . doi:10.1145/321679.321691. S2CID   2387962.
• Borodin, Allan (1977). "On relating time and space to size and depth". SIAM Journal on Computing . 6 (4): 733–744. CiteSeerX   10.1.1.394.1059 . doi:10.1137/0206054. MR   0461984.
• Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A. (1994). "On the power of randomization in on-line algorithms". Algorithmica . 11 (1): 2–14. doi:10.1007/BF01294260. MR   1247985. S2CID   26771869.

Books

• Borodin, Allan; Munro, Ian (1975). The Computational Complexity of Algebraic and Numeric Problems. Elsevier Computer Science Library; Theory of Computation Series. Vol. 1. New York, London, Amsterdam: American Elsevier Publishing Co., Inc. MR   0468309.
• Borodin, A.; El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN   978-0-521-56392-5.

See also

• Gap theorem
• Online algorithms
• Computational Complexity

References

1. "Governor General Announces 114 New Appointments to the Order of Canada". November 26, 2020.
2. Borodin named University Professor Archived 2011-09-13 at the Wayback Machine , U. Toronto Computer Science, retrieved 2012-03-17.
3. Past prizes and awards, PIMS, retrieved 2012-03-17.
4. Allan Bertram Borodin at the Mathematics Genealogy Project
5. Allan Borodin: Recipient of the 2008 CRM-Fields-PIMS Prize, retrieved 2012-03-17.
6. AAAS Members Elected as Fellows in 2011 Archived January 13, 2012, at the Wayback Machine , retrieved 2012-03-17.
7. ACM Names Fellows for Innovations in Computing Archived 2015-01-09 at the Wayback Machine , ACM, January 8, 2015, retrieved 2015-01-08.

External links

• Home Page at University of Toronto