Speaker: Allan Borodin, University of Toronto
Title: Computing (and life) is all about tradeoffs: A small sample of some computational tradeoffs
A pervasive theme in Computer Science (as in any science or for that matter in life) is tradeoffs. For example, in one form or another, time-space tradeoffs can be found in many settings. Another traditional research area concerns tradeoffs between performance (e.g. approximation bounds) verses complexity bounds. Newer areas of research consider various issues of tradeoffs involving concepts relating to fairness, privacy, conceptual simplicity, robustness, and self-interest (e.g. truthfulness). We will review some of the well established results as well as some of the many open questions involving tradeoffs.
This is a slightly modified survey talk that was presented at the Conference on Space-Efficient Data Structures, Streams and Algorithms which was a workshop at the University of Waterloo featuring talks in celebration of Ian Munro's birthday.