CS265

Welcome to CS265/CME309!

Randomized Algorithms and Probabilistic Analysis

Stanford University, Autumn 2026.

Course Overview

Instructor: Greg Valiant

CAs: Balaji Balachandran

Course Description: Randomness pervades the natural processes around us, from the formation of networks, to genetic recombination, to quantum physics. Randomness is also a powerful tool that can be leveraged to create algorithms and data structures which, in many cases, are more efficient and simpler than their deterministic counterparts. This course covers the key tools of probabilistic analysis, and application of these tools to understand the behaviors of random processes and algorithms. Emphasis is on theoretical foundations, though we will apply this theory broadly, discussing applications in machine learning and data analysis, networking, and systems. Topics include tail bounds, the probabilistic method, Markov chains, and martingales, with applications to analyzing random graphs, metric embeddings, random walks, and a host of powerful and elegant randomized algorithms.

Prerequisites: Prerequisites: CS 161 and STAT 117/118, or equivalents and instructor consent.

When/Where: Class is T/TH, 10:30am-11:50pm in CoDa B60.

Office hours.

NOTE: Office hours start in Week 2. There are no OH in Week 1, but please ask on Ed if you have a question.

  • Greg: Tuesday 2-3pm, CoDa W244.
  • Balaji: Thursday 1-2pm, Friday 11-12am, CoDa Basement.

Deviations from this schedule will be announced on Canvas.

Course Structure

CS265/CME309 is a "flipped class." This means that you will watch short recorded mini-lectures and/or read lecture notes before class, and come to class ready to engage. In class, we will do active learning to practice and further develop the material from the mini-lectures. The agendas for each class (exercises and solutions) will be posted on this website (in the class-by-class resources below).

Since a large part of learning will happen during active in-class group work, we encourage you to attend class if possible.

Exception: Please do not come to class if you are sick.

Announcements

  • Course announcements will be posted on Canvas. If you don't check Canvas regularly, please make sure your notifications are set so that you get email announcements.
  • Ed discussion forum link: https://edstem.org/us/join/BYgrmR

Useful Links

Assignments

This course will have (approximately) weekly homework (which will not be graded), and two in-person exams.

(More) Course Policies

Grading

Your grade is made up of:

  • 10% Class Participation: If you come to most classes and engage with the material and your fellow classmates, you will get all 10% of this!
  • 30% Midterm exam.
  • 60% Final exam.

There will be several options throughout the quarter for you to go above and beyond. (For example, bonus "might be fun to think about" problems, links to further reading, etc). These things do not factor directly into your grade, but they will factor into your learning! The course staff will be happy to give you feedback on any of these sorts of things, but we won't officially grade them.

Class-by-class Schedule and Assignments

Below, find class-by-class resources, including lecture notes, in-class agendas and exercises, and further reading. All videos can be found Canvas, or also on the YouTube playlist here.

Classes that have not happened yet may have broken links or links to draft (last year's) materials, and are subject to change.

9/22. Class 1: Introduction, Polynomial Identity Testing

9/24. Class 2: Karger's algorithm and the Karger-Stein algorithm

9/29. Class 3: Primality Testing

10/1. Class 4: Markov and Chebyshev inequalities; sampling-based median

10/6. Class 5: Moment generating functions; Chernoff bound; Randomized routing on the hypercube

10/8. Class 6: Balls and Bins; "Poissonization"; The power of 2 choices

10/13. Class 7: Metric Embeddings I; Bourgain's embedding

10/15. Class 8: Metric Embeddings II; Johnson-Lindestrauss Transform

10/20. Class 9: The probabilistic method I: bounding Ramsey numbers, derandomization via conditional expectations

  • Before class:
    • Mini-lecture on the probabilistic method and Ramsey numbers
    • Mini-lecture on independent sets
    • NOTE: The videos on YouTube are labelled "Class 10," not "Class 9," because this year is paced a bit differently than previous years.
    • Corresponding lecture notes
  • During class: Agenda [agenda solutions]

10/22. Class 10: The probabilistic method II: Second-moment method and the Lovasz Local Lemma

  • Before class:
    • Mini-lecture on the second-moment method
    • Mini-lecture on the LLL
    • Mini-lecture on the proof of the LLL
    • NOTE: The videos on YouTube are labelled "Class 11," not "Class 10," because this year is paced a bit differently than previous years.
    • Corresponding lecture notes
  • During class: Agenda [agenda solutions]
  • Optional further reading: excerpt from Mitzenmacher and Upfal proving the more general version of the LLL.

10/27. Class 11: In-class midterm

10/29. Class 12: The 'Constructive' LLL

11/3. No class, happy Democracy Day.

11/5. Class 13: Introduction to Markov chains; randomized algorithm for 2SAT

  • Before class:
    • Mini-lecture on Markov Chains
    • Mini-lecture on Randomized 2-SAT

      Errata:

      • At 20:18, there's an ri-1 that should be ri+1. (Fortunately the typo is fixed for the conclusion of that derivation!)
      • At 23:06 it says that Xt is the number of variables on which σ* and σt differ; it should be the number of variables on which they agree.
    • Corresponding lecture notes
  • During class: Agenda
  • Optional further reading: For more about spectral analysis of random walks, see Section 21.1 of Arora and Barak's book "Computational Complexity: A Modern Approach." You can access a digital copy through the Stanford Library. Section 21.1 relates the second eigenvalue of the transition matrix to how fast a random walk on a regular graph approaches the uniform distribution (see Lemma 21.3).
  • Agenda solutions: solutions to in-class work

11/10. Class 14: Fundamental theorem of Markov chains; stationary distributions; Markov Chain Monte Carlo

  • Before class:
    • Mini-lecture on some Markov Chain Definitions
    • Mini-lecture on the fundamental Theorem of Markov Chains
    • Mini-lecture on MCMC. ERRATUM: In the slide starting around minute 12, the labels on the diagram are a bit messed up, and this propagates into the derivation! As written, the probabilities on the diagram don't agree with the definition of P_{i,j} in the top right corner. If you fix them so that they do, everything should go through! See the lecture notes for a correct derivation. Sorry about that!
    • Corresponding lecture notes
  • During class: Agenda [agenda solutions]
  • Further (optional) reading: A survey of using Markov chains to sample random colorings

11/12. Class 15: Mixing times; strong stationary times; coupling

11/17. Class 16: Martingales; the Doob Martingale; Azuma-Hoeffding tail bounds

  • Before class:
    • Mini-lecture on Martingales
    • Mini-lecture on Azuma-Hoeffding bound. Erratum: Around 7:38, I wrote a c that should have been a c^2. (It's correct in the theorem statement!)
    • Corresponding lecture notes
  • During class: Agenda

11/19. Class 17: The martingale stopping theorem; applications