6.889 Sublinear Time Algorithms


Graduate Level
Prerequisites:  6.045J, 6.046J
Units: 3-0-9
Instructor:  Professor Ronitt Rubinfeld
Schedule:  TR11-12:30, room 24-115
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.
Principal topics include:
1. Testing and estimating properties of functions, graphs, strings and other combinatorial objects
2. Sublinear time approximations of optimization problems
3. Testing global properties of distributions
This course will 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 and probability theory.