LFCS Seminar: 5 March 2019 - Pan Peng

Title: Graph Property Testing and Random Order Streams

Abstract:

We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. We show that (1) 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; (2) for general graphs, any property that is constant-query testable in the random-neighbor model with one-sided error can be tested with constant space in a single-pass in random order streams with one-sided error. We also present a random order streaming algorithm for testing connectivity of general graphs with two-sided error.

Based on joint work with Artur Czumaj, Hendrik Fichtenberger, Morteza Monemizadeh, S. Muthukrishnan and Christian Sohler.