Lectures Mondays & Wednesdays 1:00-2:20pm, DC 2568
Instructor Eric Blais
Textbook The Probabilistic Method, Noga Alon and Joel H. Spencer


In this research- and reading-oriented graduate course, we will study the probabilistic method and its numerous applications to problems in many different areas of computer science.

The idea behind the probabilistic method itself is deceptively simple: sometimes, the best way to show that some type of object exists is not to construct one explicitly, but instead to argue that a random construction gives this type of object with non-zero probability. We will see in the course how this idea has far-reaching consequences in:

In the course, we will aim to read one chapter of the textbook per week. The Monday lectures will be devoted to presenting and discussing the main theorems of the week’s chapter. During the Wednesday lectures, we will break out into smaller groups in a problem-solving session where we apply the probabilistic method to a variety of different problems from different areas of computer science.

The final component of the course is a research project, in which each participant in the class will pursue active research on a topic related to the course.