Multi-Pass Streaming Lower Bounds for Uniformity Testing

We prove multi-pass streaming lower bounds for uniformity testing over a domain of size $2m$. The tester receives a stream of $n$ i.i.d. samples and must distinguish (i) the uniform distribution on $[2m]$ from (ii) a Paninski-style planted distribution in which, for each pair $(2i-1,2i)$, the probabilities are biased left or right by $\epsilon \mathrm{/}2m$. We show that any $\mathrm{\ell }$-pass streaming algorithm using space $s$ and achieving constant advantage must satisfy the tradeoff $sn\mathrm{\ell }=\tilde{\mathrm{\Omega }}(m\mathrm{/}{\epsilon }^2)$. This extends the one-pass lower bound of Diakonikolas, Gouleakis, Kane, and Rao (2019) to multiple passes. Our proof has two components. First, we develop a hybrid argument, inspired by Dinur (2020), that reduces streaming to two-player communication problems. This reduction relies on a new perspective on hardness: we identify the source of hardness as uncertainty in the bias directions, rather than the collision locations. Second, we prove a strong lower bound for a basic two-player communication task, in which Alice and Bob must decide whether two random sign vectors $Y^a,Y^b\in \{\pm 1{\}}^m$ are independent or identical, yet they cannot observe the signs directly–only noisy local views of each coordinate. Our techniques may be of independent use for other streaming problems with stochastic inputs.