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

Sepehr Assadi, Prantar Ghosh, Bruno Loff +2

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 t…