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
Schedule
| Lecture | Topic | Notes | Reading |
|---|---|---|---|
| Lecture 1 (03/30/2026) | Introduction, Probabilistic Method | PDF, html | Chapters 1–2 |
| Lecture 2 (04/02/2026) | Second Moment Method | PDF, html | Chapter 3 |
| Lecture 3 (04/03/2026) | DNF Counting and Reliability | PDF, html | A recent work on unreliability problem |