Janani Sundaresan -- Random Order Streaming Lower Bounds for Connected Components

Janani Sundaresan presents "Random Order Streaming Lower Bounds for Connected Components" at the DIMACS Workshop on Modern Techniques in Graph Algorithms held at Rutgers University on June 12, 2023 - June 15, 2023.

Abstract: We study the space requirement for an additive approximation of number of connected components in random order streams through the communication complexity of gap cycle counting problems. These problems have been introduced by Verbin and Yu [SODA 2011] and have found numerous applications in proving streaming lower bounds.

While noisy gap cycle counting (NGC) can be solved trivially under a random partition of edges with zero communication when k is much less than log{n}, in this talk we show that when k is a constant factor larger than log{n}, the one-way communication complexity of NGC is Omega(n) bits.

As a corollary of this result, we show that any streaming algorithm that for every eps greater than 0 estimates the number of connected components of a graph presented in a random order stream to within an eps n additive factor requires 2^{Omega(1/eps)} space.

This is joint work with Sepehr Assadi.

The DIMACS Workshop on Modern Techniques in Graph Algorithms presented major advances in the design of efficient graph algorithms that have occurred over the last decade. The goal of this workshop was to bring together researchers from different areas of graph algorithms to share the techniques that have been recently influential in their areas. Topics covered not only fast graph algorithms in the classical setting, but also algorithms in various computational models such as dynamic algorithms, streaming algorithms, and sublinear algorithms.

Видео Janani Sundaresan -- Random Order Streaming Lower Bounds for Connected Components канала DIMACS CCICADA