EUVIMEDEUVIMED entdecken
Crossref

Tight Streaming Lower Bounds for Deterministic Approximate Counting

Yichuan Wang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →