EECS 598: Randomness and Computation

Instructor: Grant Schoenebeck

GSI: Yuqing Kong

Time: Monday and Wednesday 3pm-4:30pm

Location: 1006 DOW


Randomness and the tools of probability theory have proven central in many areas of modern science, including, perhaps surprisingly, the design and analysis of algorithms. This course will be organized around the main tools and techniques (linearity of expectation, the second moment method, Chernoff bounds, martingales, Lovasz-Local Lemma, Monte Carlo Markov Chain, etc) used in probabilistic analysis of algorithms. Along the way, students will be exposed to a large variety of “classic” theoretical computer science works resulting from the applications of these same tools to both randomized algorithms and the analysis of random combinatorial objects (e.g. graphs, Boolean formulae) and deterministic algorithms applied to random inputs drawn from some distribution.

Advanced applications covered may include the Talagrand’s inequality; social networks; streaming algorithms; distributed algorithms; quantum computation; approximation algorithms; semidefinite programs; cryptographic protocols, and more. Specific advanced topics included will depend on the interests of the students.

After taking this course, students should be able to employ an array of tools for probabilistic analysis in their future research, as well understanding some of the classic applications of these techniques.

Who Should Take this Course?

If you are interested in theoretical computer science (TCS) or tools of probabilistic analysis, it should be a fun course. It will assume basic theory understanding (at the level of 376) and basic probability theory, and the methodology will be that of formal mathematical proofs. The course will be targeted as an introductory course for CSE graduate students studying theory (very broadly speaking)—though others should benefit as well, including advanced undergraduates and graduate students from other areas.

This course will count for a theory breadth requirement CSE masters and PhD students and for a depth requirement for PhD students. However, if you do not have much interest in the course topics or TCS, there are easier ways to fulfill the theory requirement (e.g. EECS 586 requires less background / rigor).

To get an understanding if you have the required background, try reading through the lecture notes in the course text section below. This course will be aimed at a similar level. You do not need to understand everything (that is what the course is for), but if you are completely lost, you will likely have a difficult and not get much out of the course.

Course Textbook:

While there is no text book, we will largely follow the lecture notes of a previous course (tailoring and updating some material) EECS 271 by Alistair Sinclair at UC Berekeley.

Course Format:

The material covered will generally be classical computer science results with an emphasis on how probabilistic analysis is used in them.

This course will seek to actively engage students at many different levels. A key principal behind the design of this course is that “teaching is the best way to learn.” The students will be involved in the teaching processes.

There will usually be reading assignments that will be read before class and discussed or otherwise engaged with in class. These reading assignments will typically be accompanied by a “worksheet” that is designed by students and graded on effort.

The lectures will be taught in a variety of ways including: instructor lecturing, presentation roulette (where students need to present sections of material—with the help of the class!), discussion, and in-class problems.

In addition to lecture prep and worksheets, there will be several problem sets, a midterm exam, a relevant recent research presentation, the presentation of a topic, and a final exam. The final exam can be skipped by successfully completing a final project.


worksheets / peer grading 15%
problem sets / peer grading 10%
midterm 15%
teaching prep and in-class leadership 14%
topic presentation 13%


relevant recent research presentation 13%
final exam 20%


Final Project 33%

More Information:

This web-site is largely so that students thinking about the course can see more about it. Please see cTools for more up-to-date information on the course.