6.889 Sketching and Streaming Algorithms for Big Data


Prereq: 6.046J (good understanding of linear algebra and probability)
Units: 3-0-9
Schedule:Lec TR2:30-4, room 32-124
Staff: Professor Piotr Indyk, indyk@mit.edu

This subject qualifies as a Theoretical Computer Science concentration subject.
Big data is data so large that it does not fit in the main memory of a single machine. The need to process big data by space-efficient algorithms arises in Internet search, machine learning, network traffic monitoring, scientific computing, signal processing, and 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. Some topics covered include streaming algorithms, dimensionality reduction and sketching, randomized algorithms for numerical linear algebra, sparse recovery and Sparse Fourier Transform.  The course will also cover applications of these methods, including wireless information transmission and neural network compression.