Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting

Ofer Grossman; Meghal Gupta; Mark Sellke

doi:10.1109/FOCS57990.2023.00091

paper

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting

arXiv:2304.01438 · doi:10.1109/FOCS57990.2023.00091

Abstract

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 (lo g lo g N)$ . We investigate the pseudo-deterministic complexity of the problem and prove a tight $I^c ◯ (lo g N)$ lower bound, thus resolving a problem of Goldwasser-Grossman-Mohanty-Woodruff.

Clarified example 2 in the technical overview. Appeared in FOCS 2023