# Characterization of problems for which sublinear time algorithms exist

I was wondering if problems for which sublinear time (in the input size) algorithms exist can be characterized as possessing specific properties. This includes sublinear time (e.g. property testing, an alternative notion of approximation for decision problems), sublinear space (e.g. sketching/streaming algorithms in which the Turing machine has a read-only tape, a sublinear working space, and a write-only output tape) and sublinear measurements (e.g. sparse recovery/compressive sensing). In particular, I am interested to such a characterization for both the framework of property testing algorithms and in the classical model of randomized and approximation algorithms.

For instance, the problems for which a dynamic programming solution exist exhibit optimal substructure and overlapping subproblems; those for which a greedy solution exists exhibit optimal substructure and the structure of a matroid. And so on. Any reference dealing with this topic is welcome.

With the exception of a few problems that admit a deterministic sub linear algorithm, almost all of the sublinear algorithms I have seen are randomized. Is there any specific complexity class related to problems admitting sublinear time algorithms ? If yes, is this class included in BPP or PCP?

• sub-linear time in which model? – Kaveh Mar 6 '12 at 21:40
• property testing algorithms are in the general framework of what you want, but Kaveh's point must be answered first. – Suresh Venkat Mar 7 '12 at 4:39
• I have edited my question adding the requested information. – Massimo Cafaro Mar 7 '12 at 6:40
• The Fourier Transform of a vector can be computed in sublinear time when it is (almost) $k$-sparse in the frequency domain. So the property here is sparsity. Check for example "Simple and Practical Algorithm for Sparse Fourier Transform" by Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price nms.lcs.mit.edu/~dina/pub/soda12.pdf and references therein. – Dimitris Mar 8 '12 at 0:26

For the constant-time task of testing graph properties, an interesting characterization is known. A graph property is a function from all graphs to $\{0,1\}$, and a graph property $P$ is testable if there is a randomized algorithm $A$ such that for all $\varepsilon > 0$ and all graphs $G$:
• $A(G)$ reads only $g(\varepsilon)$ edges of $G$ for some function $g$
• If $P(G)=1$ then $A(G)$ outputs yes'' with high probability (say, at least $2/3$)
• If at least $\varepsilon n^2$ edges of $G$ have to be added or removed in order to get a $G'$ such that $P(G')=1$ (that is, $G$ is $\varepsilon$-far from the property) then $A(G)$ outputs no'' with probability at least $2/3$
That is, $A$ can distinguish between graphs which have $P$ and graphs which have high edit distance from graphs having $P$. Alon, Fischer, Newman, and Shapira proved that a property $P$ is testable in this way if and only if the property can be "reduced" to the property of checking whether a graph has an $\varepsilon$-regular partition (in the sense of Szemeredi). This shows that testing regularity is "complete" for testing, in some sense. (There is also a one-sided error version of testability, see the reference.)