Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Pan Peng: Graph Property Testing and Random Order Streams

LFCS seminar: Pan Peng: Graph Property Testing and Random Order Streams

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When Mar 05, 2019
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal
iCal

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.

Document Actions