Tight Streaming Lower Bounds for Deterministic Approximate Counting
<|reference_start|>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 [MG82] has achieved optimal space usage.<|reference_end|>
@article{wang2024tight,
    title={Tight Streaming Lower Bounds for Deterministic Approximate Counting},
    author={Yichuan Wang},
    journal={arXiv preprint arXiv:2406.12149},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.12149},
    primaryClass={cs.DS cs.CC}
}