(Sublinear) Time Meets Space

Maybe this post should be called "property testing meets streaming". For more than a decade now we have managed to put together meetings that had both property testing folks (with methods running in time sublinear in input size) and streaming folks (with methods using space sublinear in input size), and in many of these meetings, researchers debate the nuances and results of these communities (the usual: algorithms vs complexity, for each vs for all, yaada yaada yaada). Obviously each community has learned from the other, but there were not many results that formally related the underlying concerns.

Recently, Christian, Pan, Morteza and I showed: ".. 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." This is a human-sized hop towards establishing formal connections.  Hope more hops and leaps will ensue.