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 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
Grades in this course will be based on problem sets, scribe work and a possible project.