Can I read Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy on EtoBox?

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy by Assadi, Sepehr; Ghosh, Prantar; Loff, Bruno; Mittal, Parth; Mukhopadhyay, Sagnik is a scholarly article available to read on EtoBox.

What is Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy about?

The following question arises naturally in the study of graph streaming algorithms: "Is there any graph problem which is "not too hard", in that it can be solved efficiently with total communication (nearly) linear in the number $n$ of vertices, and for which, nonetheless, any streaming algorithm with $\tilde{O}(n)$ space (i.e., a semi-streaming algorithm) needs a polynomial $n^{\Omega(1)}$ number of passes?" Assadi, Chen, and Khanna [STOC 2019] were the first to prove that this is indeed the case. However, the lower bounds that they obtained are for rather non-standard graph problems. Our first main contribution is to present the first polynomial-pass lower bounds for natural "not too hard" graph problems studied previously in the streaming model: $k$-cores and degeneracy. We devise a novel communication protocol for both problems with near-linear communication, thus showing that $k$-cores and degeneracy are natural examples of "not too hard" problems. Indeed, previous work have developed single-pass semi-streaming algorithms for approximating these problems. In contrast, we prove that any semi-streaming algorithm for exactly solving these problems requires (almost) $\Omega(n^{1/3

Author

Assadi, Sepehr; Ghosh, Prantar; Loff, Bruno; Mittal, Parth; Mukhopadhyay, Sagnik

Published

2024

Language

EN