Christian Sohler
Property Testing and Random Order Streams

Abstract: We show that every constant time testable property in
bounded degree graphs has a streaming algorithm in random order
streams. We also show some results for general graphs, in particular,
we present an algorithm for connectivity testing in general graphs.