Tight Streaming Lower Bounds for Deterministic Approximate Counting

Yichuan Wang

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…