Tight Streaming Lower Bounds for Deterministic Approximate Counting
ACM Transactions on Algorithms · 22.07.2026
DOI: 10.1145/3821634 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 22.07.2026. Verfasst von Yichuan Wang. Die Arbeit nennt 11 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Wang, Y. (2026). Tight Streaming Lower Bounds for Deterministic Approximate Counting. ACM Transactions on Algorithms. https://doi.org/10.1145/3821634
Vancouver
Wang Y. Tight Streaming Lower Bounds for Deterministic Approximate Counting. ACM Transactions on Algorithms. 2026. doi:10.1145/3821634
BibTeX
@article{Wang2026,
author = {Wang, Yichuan},
title = {Tight Streaming Lower Bounds for Deterministic Approximate Counting},
journal = {ACM Transactions on Algorithms},
year = {2026},
doi = {10.1145/3821634}
}
EUVIMED