{"ID":2845126,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.03960","arxiv_id":"2511.03960","title":"Multi-Pass Streaming Lower Bounds for Uniformity Testing","abstract":"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 $ε/2m$. We show that any $\\ell$-pass streaming algorithm using space $s$ and achieving constant advantage must satisfy the tradeoff $sn\\ell=\\tildeΩ(m/ε^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.","short_abstract":"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 l...","url_abs":"https://arxiv.org/abs/2511.03960","url_pdf":"https://arxiv.org/pdf/2511.03960v2","authors":"[\"Qian Li\",\"Xin Lyu\"]","published":"2025-11-06T01:30:56Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}