Summary
In this paper the authors study the problem of replicable uniformity testing. The non-replicable version of the problem can be stated as follows: given some $\varepsilon > 0$ and sample access to some distribution $p$ on $[n]$ what is the minimum number of samples $m$ to distinguish whether $p$ is the uniform distribution or $\varepsilon$ far from it in TV distance? A long line of work has shown that the sample complexity for this task is $\Theta(\sqrt{n}/\varepsilon^2)$. The authors ask for algorithms that have the additional replicability requirement based on the definition of Impagliazzo et al. (2022), meaning that when the algorithm is executed twice on two i.i.d. sets of samples from the same distribution it will make the same decision with probability at least $1-\rho$. The authors design an algorithm that requires $\tilde{\Theta}(\sqrt{n}/(\varepsilon^2\rho) + 1/(\varepsilon^2\rho^2))$ many samples from the distribution $p$. This bound is achieved by considering a (non-replicable) uniformity tester that is based on some $\ell_1$ statistic, since testers based on $\ell_2$ statistics would incur a $tilde{\Theta}(\sqrt{n}/(\varepsilon^2\rho^2))$ sample complexity. Moreover, they provide an (almost) matching lower bound for a natural class of "symmetric" algorithms.
Strengths
I find this work pretty interesting. I think uniformity testing is a natural application domain for the definition of replicability, since the decisions of the algorithm are binary so the discrete metric on the output space (which is what the definition is asking for) is a natural one for this problem.
Moreover, the $\sqrt{n}/(\varepsilon^2 \rho)$ sample complexity is interesting and has not appeared in the replicability line of work before.
From a technical point of view, the upper bound is achieved by a standard modification of some non-replicable algorithm using a random thresholding trick. However the correctness is based on a concentration argument that requires subtle technical work, dependent on different regimes of the parameters that come into play.
Similarly, the lower bound follows the high-level template that has been introduced by prior work. Nevertheless, the technical details are not straightforward.
I think another aspect of the results that the authors could consider highlighting is that, in this setting, replicability does not require any blow-up in the sample complexity with respect to the ambient dimension. This is in contrast with other tasks such as replicable mean estimation. The straightforward generalization of the approach of [Impagliazzo, Lei, Pitassi, Sorrell '22] to the $\ell_\infty$ estimation of the means of $n$ coins requires a blow-up of $n^2/\rho^2$ samples. There is a (computationally inefficient) approach by [Karbasi, Velegkas, Yang, Zhou '23] that shaves off a factor of $n$, and was recently shown to be optimal [Hopkins, Impagliazzo, Kane, Liu, Ye '24]. Similar results hold for the $\ell_2$ estimation.
Overall, I believe that the paper studies a useful problem, the results are interesting, and the technical contribution is above the bar for NeurIPS.
Weaknesses
I think that the discussion prior to the statement of the main result could be improved by mentioning that there is a $1/(\varepsilon^2\rho^2)$ additive term in the sample complexity (maybe even in the discussion in the abstract).
I am bit confused about how the $\tilde{O}(1/(\varepsilon^2\rho^2))$ shows up in the upper bound. The proof sketch that is presented in the main body only considers the $\tilde{O}(\sqrt{n}/(varepsilon^2\rho))$ term. I understand that this is required even for $n=2$, I just don't see how it is used in the general case. Could you please elaborate on it?