<p>In the realm of sublinear <em>space</em>, 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. </p>

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

CC BY-SA 3.0
2012-03-07T22:14:50.337Z
2012-03-07T22:14:50.337Z
Suresh Venkat
<p>For the constant-time task of testing graph properties, an interesting characterization is known. A <em>graph property</em> is a function from all graphs to $\{0,1\}$, and a graph property $P$ is <em>testable</em> if there is a randomized algorithm $A$ such that for all $\varepsilon &gt; 0$ and all graphs $G$:</p>

<ul>
<li>$A(G)$ reads only $g(\varepsilon)$ edges of $G$ for some function $g$</li>
<li>If $P(G)=1$ then $A(G)$ outputs ``yes'' with high probability (say, at least $2/3$)</li>
<li>If at least $\varepsilon n^2$ edges of $G$ have to be added or removed in order to get a $G&#39;$ such that $P(G&#39;)=1$ (that is, $G$ is <em>$\varepsilon$-far from the property</em>) then $A(G)$ outputs ``no'' with probability at least $2/3$</li>
</ul>

<p>That is, $A$ can distinguish between graphs which have $P$ and graphs which have high edit distance from graphs having $P$. <a href="http://www.tau.ac.il/~nogaa/PDFS/charac13.pdf">Alon, Fischer, Newman, and Shapira</a> proved that a property $P$ is testable in this way <strong>if and only if</strong> 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.) </p>

CC BY-SA 3.0
2012-03-07T19:04:23.953Z
2012-03-07T21:04:45.627Z
2012-03-07T21:04:45.627Z
Ryan Williams
<p>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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2012-03-06T21:40:33.027Z
sub-linear time in which model?
Kaveh
CC BY-SA 3.0
2012-03-07T04:39:22.657Z
property testing algorithms are in the general framework of what you want, but Kaveh's point must be answered first.
Suresh Venkat
CC BY-SA 3.0
2012-03-07T06:40:41.957Z
I have edited my question adding the requested information.
Massimo Cafaro
CC BY-SA 3.0
2012-03-08T00:26:13.940Z
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
<cc.complexity-theory><ds.algorithms><complexity-classes><approximation-algorithms>
Characterization of problems for which sublinear time algorithms exist
Massimo Cafaro
# Characterization of problems for which sublinear time algorithms exist

(Asked by: username_0 on 2012-03-06)

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?

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, approximation-algorithms
> **Comments:**
> **username_1**: sub-linear time in which model?  
> **username_2**: property testing algorithms are in the general framework of what you want, but Kaveh's point must be answered first.  
> **username_0**: I have edited my question adding the requested information.  
> **username_3**: 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.  

---

## 2 answers

### Answer by username_4 on 2012-03-07. Score: 13 | Accepted answer

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](http://www.tau.ac.il/~nogaa/PDFS/charac13.pdf) 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.)


---

### Answer by username_2 on 2012-03-07. Score: 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.


---

