Description
Randomness is one of the strongest tools which enables designing efficient algorithms. The applications of randomness in computer science spans machine learning algorithm, cryptography, networks, distributed systems. In this course, we study a variety of probabilistic tools and techniques that allow us to harness the power of randomness and apply it in algorithm design and learning theory.
Schedule
| Date | Material | Assignment |
|---|---|---|
| 01/13/2026 | Probability overview Notes, Logistics (slides) |
Fill out the scribe sign up sheet.
Due on Tuesday, January 20, 11:59pm (CT) |
| 01/15/2026 | Property testing, Testing sortedness (Binary Case) Notes |
|
| 01/20/2026 | Testing sortedness (General case) Notes, Reading: Section 4.3 in IPT | |
| 01/22/2026 | Concenteration of random variables, Coin bias estimation Notes | |
| 01/27/2026 |
Distribution testing: Uniformity Testing Notes Reading: Section 11 in IPT |
|
| 01/29/2026 |
Poissonization Notes Section 5.4 in Probability and Computing book | |
| 02/03/2026 |
L2-distance estimator, Distribution testing: Closeness testing Notes, | |
| 02/05/2026 |
Distribution testing: Reducing L2-norm via flattening Notes |
|
| 02/10/2026 |
Gaussian random variables, CLT, Berry-Esseen Theorem Notes |
Useful material
- Some relevant textbooks (not required):
- An Introduction to Computational Learning Theory, by Michael Kearns and Umesh Vazirani
- High-Dimensional Probability: An Introduction with Applications in Data Science, by Roman Vershynin
- Introduction to Property Testing, by Oded Goldreich
- Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, by Michael Mitzenmacher and Eli Upfal
- Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David
- Useful inequalities cheat sheet, by László Kozma
- LaTeX template for scribe notes or problem set answers