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]^{n}\) , and we are required to approximate the number of each \(j\) ’s ( \(j\in[k]\) ) in the string. Typically we require an additive error \(\leq\frac{n}{3(k-1)}\) for each \(j\in[k]\) respectively, and we are mostly interested in the regime \(n\gg k\) . We prove a lower bound result that the deterministic and worst-case \(k\) -counter approximate counting problem requires \(\Omega(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\in[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 [7] has achieved optimal space usage.