Computational Explorations of Total Variation Distance

We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance.First, we give a simple deterministic polynomial-time algorithm for checking equivalence between mixtures of product distributions, over arbitrary alphabets.This corresponds to a special case, whereby the TV distance between the two distributions is zero.Second, we prove that unless $\mathsf{NP} \subseteq \mathsf{RP}$ it is impossible to efficiently estimate the TV distance between arbitrary Ising models, even in a bounded-error randomized setting.