## Sublinear Time AlgorithmsWe 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 much better than that, since for any nontrivial problem, it would seem that an algorithm must consider all of the input in order to make a decision. However, as extremely large data sets grow more prevalent in a wide variety of settings, it is natural to wonder what one can do in sublinear time. In fact,
there has been a lot of recent interest in this direction.
Sublinear time is a daunting goal since it allows one to read only
a miniscule fraction of the input. There are problems for
which deterministic exact sublinear time
algorithms are known. However, for most natural problems the
algorithm must use randomization and must give an answer which is in
some sense approximate.
There is a growing body of work aimed at finding sublinear
time algorithms for various problems.
Recent results have shown that there are classical
optimization problems whose values can be approximated in
sublinear time. In addition, Many examples of problems that can be solved in sublinear time have been found. Several useful techniques, including the use of the Szemeredi Regularity lemma and low rank approximations of matrices, have emerged for designing sublinear algorithms. Still, the study of sublinear time algorithms is very new, and much remains to be understood about their scope, both in finding sublinear time algorithms for new problems and in finding more efficient algorithms for problems that already have sublinear time algorithms. The following contains some pointers to surveys on sublinear algorithms and property testing, as well as slides from a short introductory talk. |