## A Chasm Between Identity and Equivalence Testing with Conditional Queries

by Jayadev Acharya, Clement Canonne, and Gautam Kamath

In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., whether $D=3DD^\ast$ for an explicitly known $D^\ast$) can be done with a constant number of samples, independent of the support size $n$ -- in contrast to the required $\sqrt{n}$ in the standard sampling model. However, it was unclear whether the same held for the case of testing equivalence, where both distributions are unknown. Indeed, while the best known upper bound for equivalence testing is ${\rm polylog}(n)$, whether a dependence on the domain size $n$ is necessary was still open, and explicitly posed at the Bertinoro Workshop on Sublinear Algorithms. In this work, we answer the question in the positive, showing that any testing algorithm for equivalence must make $\Omega(\sqrt{\log\log n})$ queries in the conditional sampling model. Interestingly, this demonstrates an intrinsic qualitative gap between identity and equivalence testing, absent in the standard sampling model (where both problems have sampling complexity $n^{\Theta(1)}$).