Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena +1

Consider the following gap cycle counting problem in the streaming model: The edges of a $2$-regular $n$-vertex graph $G$ are arriving one-by-one in a stream and we are promised th…