CS369G: Lectures

Spring Quarter 2016, Stanford University
  • Here you can find detailed references and reading material related to the topics covered in class.

  • You are encouraged to study the material on your own before coming to class.

To sign up for scribing a lecture send an email to the staff list with your name and SUID. You can see which lectures are available for scribing in this document.
To scribe a lecture download the template and compile it using pdflatex to produce a pdf file. After you are done email both files to us using the staff-list.

Week 1: Counting and Moment Estimation

Tuesday 3/29: Counting Distinct elements [pdf].

Thursday 3/31: Continuing Counting, Moment estimation [pdf].

Week 2: Moment Estimation and Sketching

Tuesday 4/5: Estimating F_{k} norms for kgeq 2 [pdf].

Thursday 4/7: Estimating F_{k} moments for kin[0,2) [pdf].

Week 3: Moment Estimation and Count-Min

Tuesday 4/12: Moment estimation via Max-stability [pdf].

Thursday 4/14: Max-stability and Count-Min [pdf].

Week 4: Count and Count-Min Sketches and Applications

Tuesday 4/19: Count-Min [pdf].

Thursday 4/21: Count Sketch [pdf].

Week 5: Sparse Recovery and Sampling.

Tuesday 4/26: Sparse Recovery and Threshold Sampling [pdf].

Thursday 4/28: Priority and ell_{0}-Sampling [pdf].

Week 6: Graph Streaming

Tuesday 5/3: ell_{0} Sampling and Sketching Distances [pdf].

Thursday 5/5: Spectral Sparsifiers and Counting Triangles [pdf].

Week 7: Graph Sketching and Communication Complexity

Tuesday 5/10: Sketching for k-Connectivity and Min-Cut [pdf]

Thursday 5/12: Intro to Communication Complexity (Disjointness, Index, Gap-Hamming) and Streaming Lower Bounds [pdf]

Week 8: Streaming Lower Bounds and Locality Sensitive Hashing.

Tuesday 5/17: Gap-Hamming and Multi-pass streaming lower bounds [pdf]

Thursday 5/19: Nearest Neighbor Search and Locality Sensitive Hashing [pdf]

Week 9: Locality Sensitive Hashing and Dimensionality Reduction

Tuesday 5/24: ell_{2}-LSH and Sparse Dimensionality Reduction [pdf]

Thursday 5/26: Fast Johnson Lindenstrauss Transform (FJLT) [pdf]

Week 10: Sketching for Numerical Linear Algebra

Tuesday 5/31: Sparse Subspace Embeddings [pdf]