Finding missing items requires strong forms of randomness

Adversarially robust streaming algorithms are required to process a stream of elements and produce correct outputs, even when each stream element can be chosen as a function of earlier algorithm outputs. As with classic streaming algorithms, which must only be correct for the worst-case fixed stream, adversarially robust algorithms with access to randomness can use significantly less space than deterministic algorithms. We prove that for the Missing Item Finding problem (MIF) in streaming, the space complexity also significantly depends on what kind of randomness the algorithm may use. In contrast, the space complexity of classic streaming algorithms does not depend as strongly on the way randomness is used.

For MIF on streams of length L with elements in {1,...,n}, we show that when L = exp(sqrt log n), "random seed" robust algorithms, which only use randomness at initialization, require poly(L) bits of space, while "random tape" robust algorithms, which may make random decisions at any time, need only poly(log L) space.  When L is between n^{0.01} and sqrt n, "random tape" robust algorithms need poly(L) space, while "random oracle" robust algorithms, which can read from a long random string for free, can work in poly(log L) space. Along the way, we also give essentially optimal space lower bounds for "pseudo-deterministic" streaming algorithms, defined as algorithms that may use randomness but must produce some fixed correct output with high probability. All of our lower bound proofs require going beyond straight-up communication complexity.

This is joint work with Manuel Stoeckl (Dartmouth), who recently presented a brief version of these results at CCC 2024.