Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting Article Swipe
Related Concepts
Ofer Grossman
,
Meghal Gupta
,
Mark Sellke
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2304.01438
· OA: W4362655507
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2304.01438
· OA: W4362655507
We investigate one of the most basic problems in streaming algorithms: approximating the number of elements in the stream. In 1978, Morris famously gave a randomized algorithm achieving a constant-factor approximation error for streams of length at most N in space $O(\log \log N)$. We investigate the pseudo-deterministic complexity of the problem and prove a tight $Ω(\log N)$ lower bound, thus resolving a problem of Goldwasser-Grossman-Mohanty-Woodruff.
Related Topics
Finding more related topics…