Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting

Ofer Grossman, Meghal Gupta, Mark Sellke

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 achi…