6.896 Sublinear Time Algorithms (H)

L TR1-2:30, room 36-156
Professor Ronitt Rubinfeld, Room 32-G698, ronitt@theory.csail.mit.edu
Prereq.: 6.045J or 6.046J
3-0-9

This subject qualifies as a Theoretical Computer Science concentration subject.

We have long considered showing the existence of a linear time algorithm for a problem to be the gold standard of achievement. Indeed, it is hard to imagine doing any better than that, since for most nontrivial problems, any algorithm must consider all of the input in order to make a decision. However, as extremely large data sets grow more prevalent in a variety of settings, it is natural to wonder what one can do in *sublinear* time.

The study of sublinear time algorithms is very new, but has already been applied to problems from a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. This course will introduce many of the beautiful techniques that have been applied to analyzing such algorithms.

Principal topics include:

1. Testing properties of functions, graphs, strings and other combinatorial objects

2. Sublinear time approximations of optimization problems

3. Testing global properties of distributions

Grades in this course will be based on problem sets and scribe work.