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.
LFCS Seminar: 5 March 2019 - Pan Peng
IF 4.31/4.33