Multi-Pass Streaming Lower Bounds for Uniformity Testing
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909975678287872 |
|---|---|
| author | Li, Qian Lyu, Xin |
| author_facet | Li, Qian Lyu, Xin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03960 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Pass Streaming Lower Bounds for Uniformity Testing Li, Qian Lyu, Xin Data Structures and Algorithms Computational Complexity 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. |
| title | Multi-Pass Streaming Lower Bounds for Uniformity Testing |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2511.03960 |