Advanced Topics in Computer Science: Streaming and Sketching Algorithms

This course focuses on algorithms that compress data in a way such that certain pre-specified queries can be answered. The course covers the mathematical models, algorithm design and analysis, as well as provable limitations of efficient algorithms in those models. The topics covered in the course include counting in streams, linear sketches, graph streaming, dimensionality reduction, etc. Students are assumed to be comfortable with the analysis of algorithms, basic probability and linear algebra. No specific prior knowledge is required.