Sketching Algorithms

CS 294-165 - Fall 2020 (Syllabus)

Sketching algorithms compress data in a way that is still useful for answering some pre-specified family of queries, possibly across datasets by comparing sketches. 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:

This is a graduate course, though there may be room for a limited number of advanced undergraduate students satisfying the following prerequisites: mathematical maturity and comfort with algorithms (e.g. CS 170), discrete probability, and linear algebra.