Testing Product Distributions: A Closer Look
  We study the problems of identity and closeness testing of $n$-dimensional
product distributions. Prior works by Canonne, Diakonikolas, Kane and Stewart
(COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample
complexity bounds for non-tolerant testing over a binary alphabet: given two
product distributions $P$ and $Q$ over a binary alphabet, distinguish between
the cases $P = Q$ and $d_{\mathrm{TV}}(P, Q) > \epsilon$. We build on this
prior work to give a more comprehensive map of the complexity of testing of
product distributions by investigating tolerant testing with respect to several
natural distance measures and over an arbitrary alphabet. Our study gives a
fine-grained understanding of how the sample complexity of tolerant testing
varies with the distance measures for product distributions. In addition, we
also extend one of our upper bounds on product distributions to bounded-degree
Bayes nets.
