Allan Borodin
Allan Bertram Borodin (* 1941 ) is a Canadian computer scientist. He is a professor at the University of Toronto .
Borodin studied mathematics at Rutgers University with a bachelor's degree in 1963 and at the Stevens Institute of Technology with a master's degree in 1966. In addition, he worked from 1963 to 1966 as a systems programmer at Bell Laboratories . In 1969 he received his PhD under Juris Hartmanis at Cornell University (Computational Complexity and the Existence of Complexity Gaps). He was then an assistant professor at the University of Toronto with a full professorship from 1977. From 1980 to 1985 he headed the computer science faculty and in 2011 he became a university professor.
He deals with complexity theory (such as resource and time-space tradeoffs), connection networks in parallel computers, computer algebra and online algorithms. Independently of Boris Trakhtenbrot , he proved Borodin's gap theorem .
In 1985/86 he was Lady Davis visiting professor at the Hebrew University of Jerusalem, 1983 in Nice, 1994 at the Weizmann Institute and 1993 at MIT.
He is a member of the Royal Society of Canada (1991) and a Fellow of the American Association for the Advancement of Science (2011) and received the CRM-Fields-PIMS Prize in 2008 .
Fonts
- Computational complexity and the existence of complexity gaps, Journal of the ACM, Volume 19, 1972, pp. 158-174 (gap set)
- with Ran El-Yaniv: Online Computation and Competitive Analysis. Cambridge University Press 1998
Web links
Individual evidence
- ↑ Career data based on American Men and Women of Science , Thomson Gale 2004
- ↑ Allan Borodin in the Mathematics Genealogy Project (English)
| personal data | |
|---|---|
| SURNAME | Borodin, Allan |
| ALTERNATIVE NAMES | Borodin, Allan Bertram |
| BRIEF DESCRIPTION | Canadian mathematician |
| DATE OF BIRTH | 1941 |