Polynomial-Pass Semi-Streaming Lower Bounds for Degeneracy and k-Cores

Abstract: A (possibly multi-pass) graph streaming algorithm is called semi-streaming if it processes an n-vertex graph using O(n polylog(n)) space per pass. The following question arises naturally in the study of semi-streaming algorithms: Is there any graph problem which is “not too hard”, in the sense that it can be solved efficiently with O(n polylog(n)) total communication, but for which, nonetheless, any semi-streaming algorithm needs a polynomial n^Ω(1) number of passes? Assadi, Chen, and Khanna [STOC 2019] were the first to give an affirmative answer to this question, albeit with some rather non-standard graph problems. In this talk, I shall present the first polynomial-pass lower bounds for natural “not too hard” graph problems: finding a k-core of a graph or just the value of its degeneracy. First I shall describe a novel communication protocol for both problems with O(n polylog n) total communication, thus showing that they are indeed “not too hard.” Next, I shall describe how we prove that any semi-streaming algorithm (exactly) solving these problems requires (almost) Ω(n^{1/3}) passes. This proof uses a reduction from a generalized version of the Hidden Pointer Chasing (HPC) communication problem introduced by the aforementioned paper of Assadi, Chen, and Khanna. I shall sketch this reduction and give a high level idea of how we generalize HPC to a multilayer version called MultiHPC, whose optimal lower bound allows us to prove stronger (by a polynomial factor) semi-streaming pass lower bounds for a certain class of graph problems.

This is based on a recent joint work with Sepehr Assadi, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay.

Bio: Prantar Ghosh is a Postdoctoral Fellow at Georgetown University. He is currently visiting DIMACS, Rutgers University, where he was a Simons Postdoctoral Leader last academic year. He completed his PhD in Computer Science at Dartmouth College in 2022, following which he held a Lecturer position there over the summer. His research interests lie broadly in graph algorithms, with a special focus on streaming algorithms for massive graphs.