**Authors:** Jayadev Acharya,ClĂ©ment L. Canonne,Gautam Kamath

**ArXiv:** 1411.7346
**Document:**
PDF
DOI
**Abstract URL:** http://arxiv.org/abs/1411.7346v3
*
A recent model for property testing of probability distributions (Chakraborty
et al., ITCS 2013, Canonne et al., SICOMP 2015) enables tremendous savings in
the sample complexity of testing algorithms, by allowing them to condition the
sampling on subsets of the domain. In particular, Canonne, Ron, and Servedio
(SICOMP 2015) showed that, in this setting, testing identity of an unknown
distribution $D$ (whether $D=D^\ast$ for an explicitly known $D^\ast$) can be
done with a constant number of queries, independent of the support size $n$ --
in contrast to the required $\Omega(\sqrt{n})$ in the standard sampling model.
It was unclear whether the same stark contrast exists for the case of testing
equivalence, where both distributions are unknown. While Canonne et al.
established a $\mathrm{poly}(\log n)$-query upper bound for equivalence
testing, very recently brought down to $\tilde O(\log\log n)$ by Falahatgar et
al. (COLT 2015), whether a dependence on the domain size $n$ is necessary was
still open, and explicitly posed by Fischer at the Bertinoro Workshop on
Sublinear Algorithms (2014). We show that any testing algorithm for equivalence
must make $\Omega(\sqrt{\log\log n})$ queries in the conditional sampling
model. This demonstrates a gap between identity and equivalence testing, absent
in the standard sampling model (where both problems have sampling complexity
$n^{\Theta(1)}$).
We also obtain results on the query complexity of uniformity testing and
support-size estimation with conditional samples. We answer a question of
Chakraborty et al. (ITCS 2013) showing that non-adaptive uniformity testing
indeed requires $\Omega(\log n)$ queries in the conditional model. For the
related problem of support-size estimation, we provide both adaptive and
non-adaptive algorithms, with query complexities $\mathrm{poly}(\log\log n)$
and $\mathrm{poly}(\log n)$, respectively.
*