6.896 Sublinear Time Algorithms (H)

L TR2:30-4, Room 36-155
Professor Ronitt Rubinfeld, ronitt@csail.mi.tedu
Prereq.: 6.045J, 6.046J
3-0-9

This subject qualifies as a Theoretical Computer Science Engineering Concentration subject.

The study of sublinear time algorithms has 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