Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-254 | 15th October 2026 05:31

Parameterized Uniformity Testing in the Huge Object Model

RSS-Feed




TR26-254
Authors: Clément Canonne, Sayantan Sen, Joy Qiping Yang
Publication: 15th October 2026 08:58
Downloads: 12
Keywords: 


Abstract:

We continue the study of distribution testing in the Huge Object Model (Goldreich and Ron, 2023), focusing on the flagship question of \emph{parameterized uniformity testing}: given access to data in $\{0,1\}^n$, is its underlying probability distribution uniform on a small subset of size $m$? The focus here is on both the number of data points required (sample complexity) and the number of bits from these data points one needs to observe (query complexity). While previous work fully characterized both of these in the ``tiny support'' regime $m \ll n$, very little was understood in the ``medium-to-large'' support one ($n \leq m \ll 2^n$). Our work remedies this state of affairs, establishing the existence of a sample-query complexity tradeoff and showing that (in contrast to the tiny-support regime) adaptive algorithms can significantly outperform non-adaptive ones.



ISSN 1433-8092 | Imprint