Our increased ability to gather data has resulted in data sets so large that many of our traditional algorithmic methods break down. Sorting, or even reading the entire data set can be prohibitively expensive. Under these conditions, we cannot use our standard exact algorithms, and must be content with approximate solutions that come with strong guarantees. This course will look at a range of methods and associated algorithms that use sub-linear time in the size of their input data, as well as on data stream algorithms that can perform a number of data analyses using only a single pass through the data and much less than linear space. We will also consider the limitations of these methods.

Instructor: Paul Beame, CSE 668, beame at cs.washington.edu. Office hours: Mondays after class.

Lecture: MW 1:30-2:50    MGH 254

Resources: The website http://sublinear.info has links to open problems and links to papers and other course materials on the subject matter for this course. It will serve as the closest thing to a text for the course.