Title: What I have been doing these last 50 years and what I am doing now
Speaker: Allan Borodin, University Professor, Department of Computer Science, University of Toronto
In recognition of my being on the faculty at UT for now 50 years, I was invited to present a DLS. I thank the department for this invitation. And, moreover, I thank the department and the University for providing such a great environment. However, to paraphrase Mark Twain, any rumors of my retirement are exaggerated.
My goal is to briefly review the research topics for which I have made some contributions. These include (in more or less chronological order): Abstract Complexity Theory, Algebraic Complexity Theory, time-space tradeoffs, parallel models of computation and routing, online algorithms, conceptually simple algorithmic paradigms, and more recently, Algorithmic Game Theory/Mechanism Design and Social Choice Theory. Some more general themes in my research are precise models, tradeoffs, positive versus negative results, and more recently, trying to bridge the gap between theory and “practice''.
After receiving a PhD from Cornell University, Allan Borodin joined the recently-formed Computer Science Department at the University of Toronto in 1969. He was involved in the growth of the department as it became one of the top ten departments in North America. He served as department chair from 1980 to 1985 and later serves as the acting chair 1992-93. Since then he has continued to be active in the department administration and was one of the main proponents of the very successful MScAC applied research program. He became a University professor in 2011.
Allan Borodin is a Fellow of the Royal Society of Canada, the ACM and the American Association for the Advancement of Science. He was awarded the CRM-Fields-PIMS Prize in 2008. He has been a visiting professor at Cornell University, the University of Washington, the Hebrew University, the Technion, Tel Aviv University, the Weizmann Institute, ETH Zurich, University of Nice, MIT, and the University of Rome.