Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming

The problem of counting small subgraphs, and specifically cycles, in the streaming model received a lot of attention over the past few years. In this paper, we consider arbitrary order insertion-only streams, improving over the state-of-the-art result on counting 4-cycles. Our algorithm computes a (1+ε)-approximation by taking three passes over the stream and using space O(fracm log nε2 T1/3), where m is the number of edges in the graph and T is the number of 4-cycles.