# Lower Bounds for Pseudo-Deterministic Counting in a Stream

V. Braverman, R. Krauthgamer, Aditya Krishnan, S. Sapir · 2023-03-23

Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary -- for many streaming problems, both relaxations must be employed simultaneously, to avoid an exponentially larger (and often trivial) space complexity. A common drawback of these randomized approximate algorithms is that independent executions on the same input have different outputs, that depend on their random coins. Pseudo-deterministic algorithms combat this issue, and for every input, they output with high probability the same ``canonical'' solution. We consider perhaps the most basic problem in data streams, of counting the number of items in a stream of length at most n. Morris's counter [CACM, 1978] is a randomized approximation algorithm for this problem that uses $Ω(log⁡n/log⁡log⁡n)$ bits of space, for every fixed approximation factor (greater than 1). Goldwasser, Grossman, Mohanty and Woodruff [ITCS 2020] asked whether pseudo-deterministic approximation algorithms can match this space complexity. Our main result answers their question negatively, and shows that such algorithms must use $Ω(log⁡n/log⁡log⁡n)$ bits of space. Our approach is based on a problem that we call Shift Finding, and may be of independent interest. In this problem, one has query access to a shifted version of a known string $F∈{0,1}3n$, which is guaranteed to start with n zeros and end with n ones, and the goal is to find the unknown shift using a small number of queries. We provide for this problem an algorithm that uses  $O(n)$ queries. It remains open whether $poly(log⁡n)$ queries suffice; if true, then our techniques immediately imply a nearly-tight $Ω(log⁡n/log⁡log⁡n)$ space bound for pseudo-deterministic approximate counting.

[Read the Paper](https://www.researchgate.net/publication/369623541_Lower_Bounds_for_Pseudo-Deterministic_Counting_in_a_Stream)