Lecture Schedule

Much of the material is covered in lecture notes for a previous offering of the course, numbered CS 369G. I will be updating some of these notes as we go along.

In addition, the handwritten notes from class can be found at tinyurl.com/cs368notes.

Date	Topic	Notes
4/7	Counting distinct elements	Lecture notes Probabilistic counting algorithms for data base applications, P. Flajolet, GN Martin, JCSS, 1985. Counting Large Numbers of Events in Small Registers, R. Morris, Programming Techniques, 1978.
4/9	Distinct elements cont.	Lecture notes Counting distinct elements in a data stream, Z. Bar-Yossef et al., RANDOM 2002. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, P. Flajolet, É. Fusy, O. Gandouet, F. Meunier, AoA 2007.
4/14	Lower bounds for distinct elements, Frequency moments, Estimating F_2, Johnson-Lindenstrauss. Johnson-Lindenstrauss.	Lecture notes The space complexity of approximating the frequency moments, Alon et al. STOC 1996 Optimality of the Johnson-Lindenstrauss Lemma , Larsen and Nelson, FOCS 2017. Embeddings of Finite Metric Spaces notes, M. Goemans, 2006.
4/16	Johnson-Lindenstrauss contd., Estimating F_k for k>2. Estimating F_k for k in (0,2).	Lecture notes Lecture notes Sketching Algorithms for Big Data notes, P. Indyk, J. Nelson, 2017. One-dimensional stable distributions, V.M. Zolotarev, AMS 1976.
4/21	Lower bound for Euclidean dimension reduction. Heavy Hitters (Misra-Gries algorithm).	Lecture notes Lecture notes Problems and results in Extremal Combinatorics, Part I (Section 9), N. Alon, 2003.
4/23	Count-Min and Count-Sketch	Lecture notes Lecture notes
4/28	Sparse recovery, priority sampling	Lecture notes Lecture notes Priority sampling for estimation of arbitrary subset sums, Duffield et al., SIGMETRICS’04
4/30	L0 sampling	Lecture notes Lecture notes A unifying framework for l0-sampling, Cormode & Firmani
5/5	Connectivity and cuts in the semi-streaming Model	Lecture notes Lecture notes Graph Stream Algorithms, Andrew McGregor
5/7	Graph spanners and intro. to communication complexity	Lecture notes Lecture notes Optimal approximations of the frequency moments of datastreams, Indyk & Woodruff, STOC '05'
5/12	Communication complexity cont.	Lecture notes Lecture notes by Tim Roughgarden: here and here
5/14	Lower bounds and gap hamming	Lecture notes An information statistics approach to data stream and communication complexity, Bar-Yossef et al.
5/19	High-dimensional nearest neighbours	Lecture notes Lecture notes Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality, Har-Peled et al. On the resemblance and containment of documents, Andrei Broder Similarity Estimation Techniques from Rounding Algorithms, Moses Charikar, STOC '02
5/21	L2 subspace embedding and sketching for numerical linear algebra	Lecture notes Lecture notes
5/26	L2 subspace embedding cont.	Lecture notes
5/28	MapReduce intro, MST & Filtering	Mohsen Ghaffari's notes, Ch. 1 - 2 Filtering: a method for solving graph problems in MapReduce, Lattanzi et al., SPAA '11
6/2	Connected comp. and MST in MapReduce	Mohsen Ghaffari's notes, Ch. 3
6/4	Submodular Optimization in MapReduce	Mohsen Ghaffari's notes, Ch. 6 A New Framework for Distributed Submodular Maximization, Barbosa et al., FOCS '16 Submodular Optimization in the MapReduce Model, Liu and Vondrak, SOSA '19