Tight Streaming Lower Bounds for Deterministic Approximate Counting

We study the streaming complexity of k-counter approximate counting. In the k-counter approximate counting problem, we are given an input string in [k]ⁿ, and we are required to approximate the number of each j's (j∈[k]) in the string. Typically we require an additive error /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 Ω(klog(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(klog 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.