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/14/2025 | Probability overview, testing sortedness Notes, Logistics (slides) |
Fill out this form and scribe sign up sheet.
Due on Monday, January 20, 11:59pm (CT) |
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