Tight Streaming Lower Bounds for Deterministic Approximate Counting

We study the streaming complexity of k-counter approximate counting. In the kcounter approximate counting problem, we are given an input string in [k] n , and we are required to approximate the number of each j's (j ∈ [k]) in the string. Typically we require an additive error ≤ n 3(k-1) for each j ∈ [k] respectively, and we are mostly interested in the regime n ≫ k. We prove a lower bound result that the deterministic and worst-case k-counter approximate counting problem requires Ω(k log(n/k)) bits of space in the streaming model, while no non-trivial lower bounds were known before. In contrast, trivially counting the number of each j ∈ [k] uses O(k log n) bits of space. Our main proof technique is analyzing a novel potential function.

Our lower bound for k-counter approximate counting also implies the optimality of some other streaming algorithms. For example, we show that the celebrated Misra-Gries algorithm for heavy hitters [MG82] has achieved optimal space usage.