Welcome to the official course webpage for the Fall 2026 edition of CS 860! This is a graduate level course in theoretical computer science taught at the University of Waterloo.
What is the probabilistic method? Why should we care?
A key idea of the probabilistic method is that, to prove an object exists, we do not necessarily have to construct one. It is enough to show that a randomly chosen object has positive probability of having the desired property. Erdős famously turned this idea into a powerful method in 1947, giving a half-page proof that a complete graph on roughly (2^{k/2}) vertices can be two-colored with no monochromatic (k)-clique—even though no explicit construction of such a coloring is known.
But the probabilistic method gives us much more than existence proofs. Tools such as the second-moment method, Chernoff bounds, and martingale concentration allow us to show that random objects are typically close to their expected behavior. These ideas, for example, play a central role in the analysis of randomized algorithms.
In this course, we will take a deep dive into the probabilistic method, develop its core techniques, and explore a range of powerful applications.
Instructor: Santhoshini Velusamy (santhoshini.velusamy@uwaterloo.ca)
Lectures: Thursday 1:30 pm to 4:30 pm DC 2568
Office hours: By appointment, DC 3629
Some helpful links:
References