Testable Bounded Degree Graph Properties Are Random Order Streamable

Morteza Monemizadeh, S. Muthukrishnan, Pan Peng +1

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 degre…