Graph Property Testing and Random Order Streams

We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. We show 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. We also show some results for general graphs, in particular, we present an algorithm for connectivity testing in general graphs.

Based on two papers (ICALP 17 and SODA 18) and joint work with Morteza Monemizadeh, S. Muthukrishnan and Christian Sohler.