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.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. For example, 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. The following contains some pointers to a few surveys on sublinear algorithms and property testing, as well as slides from a short introductory talk. Many of these pointers are a bit older.
WOLA (workshop on local algorithms) has been held almost yearly since 2016. Here is a pointer to the 2025 version of it. The best place to get resources and recent pointers on sublinear algorithms is at the o(n) (little oh of n) site. |