Allan Borodin
Encyclopedia
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
.
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
professor whose research is in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and algorithms.
He has co-authored papers with some of the best researchers in computer science including his longtime friend and colleague Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
winner Stephen Cook
Stephen Cook
Stephen Arthur Cook is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity...
. Jon Kleinberg
Jon Kleinberg
-External links:**** Stephen Ibaraki*Yury Lifshits,...
, 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
Information retrieval
Information retrieval is the area of study concerned with searching for documents, for information within documents, and for metadata about documents, as well as that of searching structured storage, relational databases, and the World Wide Web...
. 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
Rutgers University
Rutgers, The State University of New Jersey , is the largest institution for higher education in New Jersey, United States. It was originally chartered as Queen's College in 1766. It is the eighth-oldest college in the United States and one of the nine Colonial colleges founded before the American...
in 1963, his M.S. in Electrical Engineering & Computer Science in 1966 from Stevens Institute of Technology
Stevens Institute of Technology
Stevens Institute of Technology is a technological university located on a campus in Hoboken, New Jersey, USA – founded in 1870 with an 1868 bequest from Edwin A. Stevens. It is known for its engineering, science, and technological management curricula.The institute has produced leading...
, and his Ph.D. in Computer Science from Cornell University
Cornell University
Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
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
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
, 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
CRM-Fields-PIMS prize
The CRM-Fields prize was given annually by the Centre de recherches mathématiques and the Fields Institute from 1994 to 2005. From 2006the Pacific Institute for the Mathematical Sciences joined the other two institutes awarding the prize, making the CRM-Fields-PIMS Prize.The prize is given for...
.
See also
- Gap theoremGap theoremIn computational complexity theory the Gap Theorem is a major theorem about the complexity of computable functions.It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes...
- Online algorithmOnline algorithmIn 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 offline algorithm is given the whole problem data from...
s - Computational ComplexityComputational complexity theoryComputational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...