A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, \ell_2 approximation, finding a nonzero entry in a vector (for turnstile algorithms) ... more >>>