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 | Testing sortedness Notes |
|
| 01/20/2026 | Testing sortedness (General case) Notes, Reading: Section 4.3 in IPT | |
| 01/22/2026 | Coin bias estimation and Concenteration of random variables Notes | |
| 01/28/2026 |
Distribution testing: uniformity Notes Reading: Section 11 in IPT |
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