Allan Borodin

Allan Bertram Borodin (* 1941) ist ein kanadischer Informatiker. Er ist Professor an der University of Toronto.

Borodin studierte Mathematik an der Rutgers University mit dem Bachelor-Abschluss 1963 und am Stevens Institute of Technology mit dem Master-Abschluss 1966. Daneben arbeitete er 1963 bis 1966 als Systemprogrammierer an den Bell Laboratories. 1969 wurde er bei Juris Hartmanis an der Cornell University promoviert (Computational Complexity and the Existence of Complexity Gaps). Danach war er Assistant Professor an der University of Toronto mit einer vollen Professur ab 1977. 1980 bis 1985 stand er der Informatik Fakultät vor und 2011 wurde er University Professor.

Er befasst sich mit Komplexitätstheorie (wie Resource- und Time-Space-Tradeoffs), Verbindungsnetzwerke in Parallelrechnern, Computeralgebra und Online Algorithmen. Unabhängig von Boris Trakhtenbrot bewies er den Lückensatz von Borodin.

1985/86 war er Lady Davis Gastprofessor an der Hebräischen Universität Jerusalem, 1983 in Nizza, 1994 am Weizmann-Institut und 1993 am MIT.

Er ist Mitglied der Royal Society of Canada (1991) und Fellow der American Association for the Advancement of Science (2011) und erhielt 2008 den CRM-Fields-PIMS Prize.

Schriften

• Computational complexity and the existence of complexity gaps, Journal of the ACM, Band 19, 1972, S. 158–174 (Lückensatz)
• mit Ran El-Yaniv: Online Computation and Competitive Analysis. Cambridge University Press 1998

Weblinks

• Homepage