Lecture  Topic  Notes  Reading  Files 
Lecture 1 (01/04/17)  Introduction, Contraction Algorithm 
pdf  MR section 1.1  
Lecture 2 (01/09/17)  Sampling, Concentration Bounds 
pdf  A list of concentration inequalities  
Lecture 3 (01/11/17)  Concentration Bounds, Hash Functions 
pdf   
(01/16/17)  No class: Martin Luther King Day 
Lecture 4 (01/18/17)  Hashing 
Pdf  The two tier hashing Algorithm paper Notes by Jeff Erickson Notes by Sanjeev Arora Summer School on Hashing  
Lecture 5 (01/23/17)  Streaming 
pdf  [AMS] paper Chapter of 1 of Roughgarden's course  
Lecture 6 (01/25/17)  Locally Sensitive Hashing 
pdf  A survey by Bernard Chazelle IndykMotwani's Paper
Charikar's Paper
Data Dependent Hashing for NNS  
Lecture 7 (01/30/17)  ShwartzZippel Lemma, Perfect Matching 
pdf  Derandomized Polynomial Identity testing implies Amazing result in Complexity Theory Harvey's algebraic algorithm
Bipartite matching is in quasiNC
 
Lecture 8 (02/01/17)  Linear Algebra Background, Low Rank Approximation 
pdf  see Trevisan's lecture note for background on spectral theorem  
(02/06/17)  No class: Due to Snow 
Lecture 9 (02/08/17)  Max cut, Spectral Graph Theory 
pdf  Sections 3.13.4 of HopcroftKannan
Column subset selection
Paper 1 Paper 2 on Low rank approximation in Almost linear time
A markov chain algorithm for column subset selection
A theoretical result on nonnegative matrix factorization
 Matlab code Image 
Lecture 10 (02/13/17)  Max Cut, The Laplacian Matrix 
pdf  HopcroftKannan Chapter 5 of KannanVempala
Goemans and Williamson Approximation Algorithm for maxcut
 
Lecture 11 (02/15/17)  Spectral Partitioning, Cheeger's Inequality 
pdf  Trevisan's spectral graph theory course
Spielman's spectral graph theory course
Higher order Cheeger inequalities
k median and k center on planar graphs
Trevisan's lecture notes on log(n) approximation for sparsest cut
 
(02/20/17)  No Class: Presidents Day 
Lecture 12 (02/22/17)  Cheegers Inequality, Power Method 
pdf  Spectral Clustering
My lecture notes on Harder direction of Cheeger's inequality
 
Lecture 13 (02/27/17)  Power Method, Random Walks, 
pdf 
See here and here for fast Laplacian solvers
See here for applciatons of fast Laplacian solvers in MaxFlow
 Graph Draw, Grid, carbon
A zip file of image segmentation files

Lecture 14 (02/01/17)  Random Walks, Linear Programming 
pdf  An application of random walks in counting
See here and here for applications random walks in local graph clustering
See here for fastest known algorithms for solving LPs
 
Lecture 15 (03/06/17)  LP Rounding, MDPs 
pdf  Applications of LPs in Approximation Algorithms  
Lecture 16 (03/08/17)  Duality and Applications 
  