Date  Topic  Slides  Reading 
26 July  Highdimensional space  Chapter 1  
28 July  Highdimensional space: Tail bounds, Volume of unit ball  Chapter 1  
02 Aug  Highdimensional space: Volume of unit ball  Chapter 1  
04 Aug  Highdimensional space: Random projection and JohnsonLindenstrauss  Chapter 1  
16 Aug  Singular Value Decomposition  Chapter 2  
18 Aug  Singular Value Decomposition  Chapter 2  
23 Aug  Singular Value Decomposition 
Chapter 2 Additional notes 

25 Aug  Singular Value Decomposition, Expander 
Chapter 2 Luca Trevisan notes 

06 Sep  Spectral Graph Theory: Basic results  Luca Trevisan notes  
08 Sep  Spectral Graph Theory: Cheeger inequality and Quiz1  Luca Trevisan notes  
13 Sep  Spectral Graph Theory: Cheeger inequality  Luca Trevisan notes  
15 Sep  Machine Learning: Generalisation  Chapter 5  
20 Sep  Machine Learning: Generalisation, VCdimension  Chapter 5  
03 Oct  Machine Learning: Generalisation, VCdimension, Sauer’s Lemma  Chapter 5  
11 Oct  Machine Learning: VCdimension, Online Learning  Chapter 5  
11 Oct  Machine Learning: Online Learning, Perceptron, Boosting  Chapter 5  
25 Oct  Streaming/Sketching: Reservoir sampling, distinct elements  Chapter 6  
27 Oct  Streaming/Sketching: Distinct elements, majority element and Quiz2  Chapter 6  
01 Nov  Streaming/Sketching: Frequent element, estimating second moment  Chapter 6  
03 Nov  Streaming/Sketching: Sketch for multiplication, CUR decomposition  Chapter 6  
08 Nov  Topic Modeling: Idealised model(pure topics)  Chapter 9  
10 Nov 
Topic Modeling: NMF using anchor terms, Social Choice: Arrow’s impossibility 
Chapter 10  
11 Nov 
Social Choice: Arrow’s impossibility, Compressed sensing 
Chapter 10  
15 Nov  Semidefinite Program: Maxcut problem 
Link 1 Link 2 

17 Nov  Quiz3 