CS 860: Randomized Complexity Theory
University of Waterloo, Winter 2025
Guinevere, Random Number Selector (cropped) by the Science Museum, London / CC BY 4.0
Preface
Complexity theory is concerned with exploring the absolute limits of computers that have bounded resources available to them. Or, to look at it from a different angle, it studies the minimum amount of resources that are needed to solve various problems.
Randomized complexity theory is the branch of complexity theory that focusses on computational models where algorithms have the ability to generate some random bits. In some computational models, this ability has a dramatic impact on what computers can do. In others, it makes no difference at all. And in yet other settings, determining whether randomness helps or not remains an open problem to this day.
In this course, we will explore the power of randomness in a variety of different models, including query complexity (or decision trees), communication complexity, time complexity, and space complexity. Our main focus will be on developing a rich set of tools for analyzing randomized algorithms and computational models.
Lecture Notes
Lecture notes for the class will be added here throughout the course, as they are completed.