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) |
| 01/16/2025 | Testing sortedness (cont.) Notes, Section 4.3 in IPT |
Problem set 1
Due on Tuesday, January 28, 11:59pm (CT) |
| 01/21/2025 | Class cancelled due to weather condition | |
| 01/23/2025 | Coin bias estimation and Concenteration of random variables Notes | |
| 01/28/2025 |
Distribution testing: uniformity Notes, Reading: Section 11 in IPT |
|
| 01/30/2025 |
Poissonization Notes, Section 5.4 in Probability and Computing book | |
| 02/04/2025 |
Distribution testing: closeness testing Notes, |
Problem set 2
Due on Tuesday, February 25, 11:59pm (CT) |
| 02/06/2025 |
Distribution testing: Reducing L2-norm via flattening Notes |
|
| 02/11/2025 |
Gaussian distribution, CLT, Berry-Esseen Theorem |
|
| 02/06/2025 |
Sub-Gaussian random variables Reading: Section 2.5 in HDP |
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