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

by Jayadev Acharya, Clement Canonne, and Gautam Kamath

#### Oded's comments

The separation result shown here refers to the model of
Conditional Samples in Distribution Testing,
and it is a separation between the complexity of testing that a
given/input distribution is identical to a fixed distribution
and the complexity of testing that a pair of given/input distribution
are identical (or equivalent).

#### The original abstract

A recent model for property testing of probability distributions 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 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)}$).

Turning to another question, we strengthen a result of Ron and Tsur on
support size estimation in the conditional sampling model, with an
algorithm to approximate the support size of an arbitrary distribution.
This result matches the previously known upper bound in the restricted case
where the distribution is guaranteed to be uniform over a subset.
Furthermore, we settle a related open problem of theirs, proving tight
lower bounds on support size estimation with non-adaptive queries.

ECCC TR14-156.

Back to
list of Oded's choices.