## Oct 22: Intro | |

Presentation of main theme of course. Basic tail inequalities, warmup for sketching (Morris's algorithm). | |

Morris's Algorithm - Robert Morris. Counting Large Numbers of Events in Small Registers http://dl.acm.org/citation.cfm?id=359627 |

## Oct 29: Sketching I | |

Distinct elements, AMS sketch | |

Lecture2.pdf 170 KB | |

The space complexity of approximating the frequency moments http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf |

## Nov 5: Sketching II | |

F2 Sketch (from AMS lecture) Continued element frequency sketching: CountSketch, CountMin sketch. | |

Lecture3.pdf 175 KB | |

In addition to reading the AMS paper, you are encouraged to complement your knowledge by reading: Finding Frequent Items in Data Streams, M. Charikar., K. Chen and M. Farach-Colton, in Proceedings of the 29th International Colloquium on Automata Languages and Programming, (2002). An improved data stream summary: the count-min sketch and its applications G. Cormode and S. Muthukrishnan Journal of Algorithms Volume 55 Issue 1, April 2005 Pages 58-75 |

## Nov 12: (Classic) JL lemma | |

JL Lemma (For proof we'll need: Norms, Minkowski's inequality, Hanson-Wright lemma) | |

Lecture4.pdf 62107 Bytes | |

Reading: "Friendly" version of the JL lemma: Dmitris Achlioptas Database-friendly random projections PODS'01 Less "friendly" version which is the source (warning: not an easy read): W. B. Johnson and J. Lindenstrauss Extensions of Lipschitz mappings into a Hilbert space Contemporary Mathematics 26:189--206, 1984 Another important classic: David Lee Hanson and Farroll Tim Wright. A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist., 42(3):1079{1083, 1971 |

## Nov 19: Fast JL | |

Fast JL algorithm (Ailon-Chazelle version) with partial proof | |

Lecture5.pdf 183 KB |

## Nov 26: Sparse JL |

## Dec 7: Compressed sensing, RIP and relation to JL | |

Including Krahmer-Ward theorem with proof sketch | |

http://statweb.stanford.edu/~candes/papers/StableRecovery.pdf | |

Lecture was based on: Emmanuel J. Candès, Justin K. Romberg, Terence Tao: Stable Signal Recovery from Incomplete and Inaccurate Measurements. Communications on Pure and Applied Mathematics Volume 59, Issue 8, pages 1207–1223, August 2006 |

## Dec 10: Matrices I | |

SVD and low rank approximations (column sampling based, JL-based) | |

Papers: Petros Drineas, Ravi Kannan, Michael Mahoney. Fast Monte Carlo Algorithms for Matrices Approximating Matrix Multiplication. SIAM J. Computing 36, 2006 Edo Liberty, Simple and deterministic matrix sketching. KDD 2013: 581-588 |

## Dec 24: Matrices II | |

Matrix completion via trace norm minimization, SVT (singular value thresholding) |

## Dec 31: SVT (continued) | |

Partial proof of Singular Value Thresholding (SVT) Paper: Cai, Candes, Shen, A Singular Value Thresholding Algorithm for Matrix Completion Introduction to MapReduce with some simple problems. |

## Jan 7: Map Reduce Continued | |

More Map-Reduce examples from: H. Karloff, S. Suri, S. Vassilvitskii: A Model of Computation for MapReduce S. Suri and S. Vassilvitskii: Counting triangles and the curse of the last reducer U Kang, C. Tsourakakis, A. P. Appel, C. Faloutsos, J. Leskovec: HADI: Fast Diameter Estimation and Mining in Massive Graphs with Hadoop |

## Jan 14: Lower bounds |

## Jan 21: Presentation of new paper or student project presentations |