6.889 Sublinear Time Algorithms


Graduate Level
Units: 3-0-9
Prerequisites:  6.046 or equivalent
Instructor:  Professor Ronitt Rubinfeld (ronitt@csail.mit.edu)
Schedule:  Lectures MW1-2:30, room 34-301
This subject counts as a Theoretical Computer Systems concentration subject.
When processing large data sets, it can be crucial to understand properties of the data after viewing only a miniscule fraction of it.  The study of sublinear time algorithms combines emerging tools from mathematics, Computer Science and statistics.    In this course we will cover the following topics:
1. Testing and estimating properties of functions, graphs, strings and other combinatorial objects
2. Sublinear time approximations of combinatorial optimization problems
3. Testing and estimating global properties of distributions:  including similarity to other distributions (variants of hypothesis testing), information theoretic and shape properties.

We introduce many of the beautiful techniques that have been applied to analyzing such algorithms, including  Fourier Analysis on the Boolean cube, Szemeredi's regularity lemma, and other tools from number theory, combinatorics, linear algebra, optimization theory, distributed algorithms, statistical tools and probability theory.