CS 229R: Algorithms for Big Data (Fall 2015, Harvard Univ.). Instructor: Professor Jelani Nelson. Big data is data so large that it does not fit in the main memory of a single machine, and the need to process big data by efficient algorithms arises in Internet search, network traffic monitoring, machine learning, scientific computing, signal processing, and several other areas.
This course will cover mathematically rigorous models for developing such algorithms, as well as some provable limitations of algorithms operating in those models. Topics discussed will include sketching and streaming, dimensionality reduction, numerical linear algebra, compressed sensing, and external memory and cache-obliviousness.
(from harvard.edu)

Lecture 03 - Necessity of randomized/approximate guarantees, Linear sketching

Necessity of randomized/approximate guarantees, Linear sketching, AMS sketch, P-stable sketch 0<p<2