Multi-Pass Streaming Lower Bounds for Uniformity Testing

Qian Li, Xin Lyu

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 unifor…