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/09/2024  Probability overview, testing sortedness Notes, Logistics (slides) 
Fill out this form and scribe sign up sheet.
Due on Monday, January 15, 11:59pm (CT) 
01/11/2024  Testing sortedness (cont.), concenteration of r.v. , coin bias estimation Notes, Section 4.3 in IPT 
Problem set 1
Due on Thursday, January 25, 11:59pm (CT) 
01/16/2024  Class cancelled due to weather condition  
01/18/2024 
Distribution testing: uniformity Notes, Reading: Section 11 in IPT 

01/23/2024 
Poissonization Notes  
01/25/2024 
Distribution testing: closeness testing Notes (Same file as the previous lecture)  
01/30/2024 
Distribution testing: Reducing L2norm via flattening Notes (Same file as the previous lecture) 

02/01/2024 
Gaussian distribution, CLT, BerryEsseen Theorem Notes 
Problem set 2
Due on Saturday, February 17, 11:59pm (CT) 
02/06/2024 
SubGaussian random variables Notes, Reading: Section 2.5 in HDP 

02/08/2024  No class (Monday's schedule)  
02/13/2024 
Subexponential random variables Notes, Reading: Section 2.7 in HDP 

02/15/2024 
Subexponential random variables (cont.), Bernstein condition, Bernstein's inequality Notes 

02/20/2024 
JohnsonLindenstrauss lemma Notes, Reading: Section 5.3 in HDP 

02/22/2024 
Linnear regression Notes 
Project guidelines is posted.
Proposal is due on Thursday, March 07, 11:59pm (CT) 
02/27/2024 
PAC learning Notes, Scribe notes, Reading: Chapter 1 of ICLT 

02/29/2024 
PAC learning, Uniform convergence Notes, Scribe notes, Reading: Section 4 of UML 

03/05/2024 
Uniform convergence (cont.), No free lunch theorem Notes, Scribe notes, Reading: Section 4 and 5 of UML 

03/07/2024 
VC dimension, Fundamental theorem of PAC learning, SauerShelahPerles lemma Notes, Scribe notes, Reading: Section 4 and 6 of UML 

03/12/2024  No class (Spring break)  
03/14/2024  No class (Spring break) 
Problem set 3
Due on Tuesday, April 2, 11:59pm (CT) 
03/19/2024 
Fundamental theorem of PAC learning (cont.) Notes (same file as the previous lecture), Scribe notes, Reading: Section 4 and 6 of UML 

03/21/2024 
Fundamental theorem of PAC learning (cont.), Learning in the presence of noise Scribe notes, Reading: Chapter 5 of ICLT 

03/26/2024 
Learning boolean conjunctions, Statistical query model Scribe notes, Reading: Chapter 5 of ICLT 

03/28/2024 
Learning in SQ model => learning in presence of noise Scribe notes, Reading: Chapter 5 of ICLT 

04/02/2024 
Weak learning => Strong learning Scribe notes, Reading: Section 10 of UML 

04/04/2024 
Adaboost Scribe notes, Reading: Section 10 of UML 

04/09/2024 
Computational hardness of PAC learning: Learning 3term DNFs Scribe notes, Reading: Chapter 1.4 of ICLT 

04/11/2024 
Special topic: differential privacy
Scribe notes A good book: The Algorithmic Foundations of Differential Privacy 
Problem set 4
Due on Friday, April 19, 11:59pm (CT) 
04/16/2024  Project presentations  
04/18/2024  Project presentations 
Useful material
 Some relevant textbooks (not required):
 An Introduction to Computational Learning Theory, by Michael Kearns and Umesh Vazirani
 HighDimensional 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 ShalevShwartz and Shai BenDavid
 Useful inequalities cheat sheet, by László Kozma
 LaTeX template for scribe notes or problem set answers