Allan Borodin

Allan Borodin
Född	1941 (81–82 år)
Alma mater	Rutgers University Stevens Institute of Technology Cornell University
Utmärkelser	ACM Fellow (2014) Order of Canada (2020)
Vetenskaplig karriär
Fält	Teoretisk datavetenskap
institutioner	University of Toronto
Avhandling	Computational Complexity and the Existence of Complexity Gaps (1969)
Doktorand rådgivare	Juris Hartmanis
Hemsida	www .cs .toronto .edu /~bor /

Allan Bertram Borodin CM (född 1941) är en kanadensisk-amerikansk datavetare som är professor vid University of Toronto .

Biografi

Borodin gjorde sina grundstudier vid Rutgers University och tog en kandidatexamen i matematik 1963. Efter att ha tagit en magisterexamen vid Stevens Institute of Technology 1966 (samtidigt som han arbetade deltid som programmerare på Bell Laboratories ), fortsatte han hans doktorandstudier vid Cornell University och avslutade en doktorsexamen 1969 under ledning av Juris Hartmanis . Han började på Toronto-fakulteten 1969 och befordrades till professor 1977. Han fungerade som institutionsordförande från 1980 till 1985 och blev universitetsprofessor 2011.

Pris och ära

Borodin valdes in som medlem av Royal Society of Canada 1991. 2008 vann han CRM-Fields-PIMS-priset . Han blev stipendiat i American Association for the Advancement of Science 2011, och stipendiat i Association for Computing Machinery 2014 "För bidrag till teoretisk datavetenskap i komplexitet , onlinealgoritmer , resursavvägningar och modeller för algoritmiska paradigm ." 2020 fick han Kanadas orden .

Utvalda publikationer

Forskningsartiklar

•    Borodin, Allan (1972). "Beräkningskomplexitet och förekomsten av komplexitetsluckor". Journal of the ACM . 19 (1): 158–174. CiteSeerX 10.1.1.453.2374 . doi : 10.1145/321679.321691 . S2CID 2387962 .
•    Borodin, Allan (1977). "Om att relatera tid och rum till storlek och djup". 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). "Om kraften i randomisering i onlinealgoritmer". Algoritmik . 11 (1): 2–14. doi : 10.1007/BF01294260 . MR 1247985 . S2CID 26771869 .

Böcker

•   Borodin, Allan; Munro, Ian (1975). Beräkningskomplexiteten hos algebraiska och numeriska problem . Elsevier datavetenskapsbibliotek; Theory of Computation Series. Vol. 1. New York, London, Amsterdam: American Elsevier Publishing Co., Inc. MR 0468309 .
•   Borodin, A .; El-Yaniv, R. (1998). Onlineberäkning och konkurrensanalys . Cambridge University Press. ISBN 978-0-521-56392-5 .

Se även

• Gapsats
• Online algoritmer
• Beräkningskomplexitet

externa länkar

• Hemsida vid University of Toronto