  We study which property testing and sublinear time algorithms can be
transformed into graph streaming algorithms for random order streams. Our main
result is that for bounded degree graphs, any property that is constant-query
testable in the adjacency list model can be tested with constant space in a
single-pass in random order streams. Our result is obtained by estimating the
distribution of local neighborhoods of the vertices on a random order graph
stream using constant space.
  We then show that our approach can also be applied to constant time
approximation algorithms for bounded degree graphs in the adjacency list model:
As an example, we obtain a constant-space single-pass random order streaming
algorithms for approximating the size of a maximum matching with additive error
$\epsilon n$ ($n$ is the number of nodes).
  Our result establishes for the first time that a large class of sublinear
algorithms can be simulated in random order streams, while $\Omega(n)$ space is
needed for many graph streaming problems for adversarial orders.
