Computational Explorations of Total Variation Distance

Abstract

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.

17 pages