In this course, we study the basics of probabilistic combinatorics with modern applications in the theory of computing.
Administrative Information
Instructor: Shayan Oveis Gharan
Office Hours: Tue 11:30–12:20, Allen Center 636
Lectures: Tue–Thu 10:00–11:20 in ECE 003, additional lectures Fri (Apr 3rd, 24th) 10:00-11:20 ECE 045
Teaching Assistants
- Dante Tjowasi, Office hour: Gates Center 151, Wednesdays, 10-11 am
Course evaluation: Homework (~80%), Final project (~20%).
Assignments
Final Project
Related Materials
Class notes
Sribble notes
Schedule
| Lecture | Topic | Notes | Reading |
|---|---|---|---|
| Lecture 1 (03/30/2026) | Introduction, Probabilistic Method | PDF, video, html | Chapters 1–2 |
| Lecture 2 (04/02/2026) | Second Moment Method | PDF, video, html | Chapter 3 |
| Lecture 3 (04/03/2026) | Strong Concentration, Giant Connected Component | PDF, video, html | Chapter 4 of Alon-Spencer |
| Lecture 4 (04/06/2026) | DNF Counting and Reliability | PDF, video, html | A recent work on unreliability problem |
| No lectures on 04/09, 04/14, and 04/16, instructor traveling | |||
| Lecture 5 (04/21/2026) | Lovasz Local Lemma | pdf,, video html | Chapter 5 of the Alon-Spencer Book Local Lemma and Maximizing Fairness |
| Lecture 6 (04/23/2026) | Algorithmic Lovasz Local Lemma | pdf, video, html | A generalization of Moser-Tardos argument |
| Lecture 7 (04/24/2026) | Positive/Negative Correlation | pdf, html, video | |
| Lecture 8 (4/28/2026) | Real Stable Polynomials (intro) | video | Strongly Rayleigh Distributions, Applications to TSP |
| Lecture 9 (04/30/2026) | Algorithmic Applications | ||
| Lecture 10 (05/05/2026) | Martingales | ||