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, property testing , an alternative notion of approximation for decision problems, has been applied to give sublinear algorithms for a wide variety of problems. One can also test various properties of distributions, where access to the distribution is given through samples generated according to the distribution, in time sublinear in the size of the support of the distribution. 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 a few surveys on sublinear algorithms and property testing, as well as slides from a short introductory talk. Some of these pointers are a bit older.
|