  Total variation distance (TV distance) is a fundamental notion of distance
between probability distributions. In this work, we introduce and study the
problem of computing the TV distance of two product distributions over the
domain $\{0,1\}^n$. In particular, we establish the following results.
  1. The problem of exactly computing the TV distance of two product
distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other
distance measures such as KL, Chi-square, and Hellinger which tensorize over
the marginals leading to efficient algorithms.
  2. There is a fully polynomial-time deterministic approximation scheme
(FPTAS) for computing the TV distance of two product distributions $P$ and $Q$
where $Q$ is the uniform distribution. This result is extended to the case
where $Q$ has a constant number of distinct marginals. In contrast, we show
that when $P$ and $Q$ are Bayes net distributions, the relative approximation
of their TV distance is $\mathsf{NP}$-hard.
