16

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Massimo Cafaro
  • 2,216
  • 20
  • 19
  • 5
    sub-linear time in which model? – Kaveh Mar 06 '12 at 21:40
  • 1
    property testing algorithms are in the general framework of what you want, but Kaveh's point must be answered first. – Suresh Venkat Mar 07 '12 at 04:39
  • I have edited my question adding the requested information. – Massimo Cafaro Mar 07 '12 at 06: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 http://nms.lcs.mit.edu/~dina/pub/soda12.pdf and references therein.

     – Dimitris Mar 08 '12 at 00:26

2 Answers2

13

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.)

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
5

In the realm of sublinear space, there's no explicit class of problems that admit a sublinear space solution, but there are large classes of problems (frequency moment estimation, dimensionality reduction etc) where the existence of a small "sketch" can be shown and this leads to efficient algorithms.

But in this space as well, the algorithms are all randomized, and there are strong deterministic lower bounds mostly based on communication complexity.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271