Allan Bertram Borodin (born 1941) is a Canadian-American
computer scientist
A computer scientist is a person who is trained in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (a ...
who is a professor at the
University of Toronto
The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...
.
[Borodin named University Professor](_blank)
, U. Toronto Computer Science, retrieved 2012-03-17.[Past prizes and awards](_blank)
PIMS, retrieved 2012-03-17.
Biography
Borodin did his undergraduate studies at
Rutgers University
Rutgers University (; RU), officially Rutgers, The State University of New Jersey, is a public land-grant research university consisting of four campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's College, and was ...
, earning a bachelor's degree in mathematics in 1963. After earning a master's degree at the
Stevens Institute of Technology
Stevens Institute of Technology is a private research university in Hoboken, New Jersey. Founded in 1870, it is one of the oldest technological universities in the United States and was the first college in America solely dedicated to mechanical ...
in 1966 (while at the same time working part time as a programmer at
Bell Laboratories
Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984),
then AT&T Bell Laboratories (1984–1996)
and Bell Labs Innovations (1996–2007),
is an American industrial Research and development, research and scientific developm ...
), he continued his graduate studies at
Cornell University
Cornell University is a private statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to tea ...
, completing a doctorate in 1969 under the supervision of
Juris Hartmanis
Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which establishe ...
.
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.
Awards and honors
Borodin was elected as a member of the
Royal Society of Canada
The Royal Society of Canada (RSC; french: Société royale du Canada, SRC), also known as the Academies of Arts, Humanities and Sciences of Canada (French: ''Académies des arts, des lettres et des sciences du Canada''), is the senior national, bil ...
in 1991. In 2008 he won the
CRM-Fields-PIMS prize
The CRM-Fields-PIMS Prize is the premier Canadian research prize in the mathematical sciences. It is awarded in recognition of exceptional research achievement in the mathematical sciences and is given annually by three Canadian mathematics instit ...
.
He became a fellow of the
American Association for the Advancement of Science
The American Association for the Advancement of Science (AAAS) is an American international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific respons ...
in 2011, and a fellow of the
Association for Computing Machinery
The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...
in 2014 ''"For contributions to
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
in
complexity
Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence.
The term is generally used to ch ...
,
on-line algorithms, resource tradeoffs, and models of algorithmic paradigms."'' In 2020 he received the
Order of Canada
The Order of Canada (french: Ordre du Canada; abbreviated as OC) is a Canadian state order and the second-highest honour for merit in the system of orders, decorations, and medals of Canada, after the Order of Merit.
To coincide with the cen ...
.
Selected publications
;Research articles
*
*
*
;Books
*
*
See also
*
Gap theorem
:''See also Gap theorem (disambiguation) for other gap theorems in mathematics.''
In computational complexity theory, the Gap Theorem, also known as the Borodin–Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable fun ...
*
Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
In contrast, an o ...
s
*
Computational Complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
References
External links
Home Page at University of Toronto
1941 births
Living people
University of Toronto faculty
American computer scientists
Rutgers University alumni
Stevens Institute of Technology alumni
Cornell University alumni
Fellows of the Royal Society of Canada
Fellows of the American Association for the Advancement of Science
Fellows of the Association for Computing Machinery
Theoretical computer scientists
Members of the Order of Canada
{{US-mathematician-stub