# Total Variation Distance for Product Distributions is
$\\#\mathsf{P}$-Complete††thanks: An extended version of this paper appeared
in the proceedings of IJCAI 2023 [BGM+23].

Arnab Bhattacharyya
National University of Singapore  Sutanu Gayen
IIT Kanpur  Kuldeep S. Meel
University of Toronto  Dimitrios Myrisiotis
CNRS@CREATE LTD  A. Pavan
Iowa State University  N. V. Vinodchandran
University of Nebraska-Lincoln

###### Abstract

We show that computing the total variation distance between two product
distributions is $\\#\mathsf{P}$-complete. This is in stark contrast with
other distance measures such as Kullback–Leibler, Chi-square, and Hellinger,
which tensorize over the marginals leading to efficient algorithms.

##  1 Introduction

Given two distributions $P$ and $Q$ over a finite domain $\mathcal{D}$, their
total variation (TV) distance or statistical difference $d_{\mathrm{TV}}(P,Q)$
is defined as

$d_{\mathrm{TV}}(P,Q)=\max_{S\subseteq\mathcal{D}}\\!\left(P(S)-Q(S)\right)=\frac{1}{2}\sum_{x\in\mathcal{D}}|P(x)-Q(x)|=\sum_{x\in\mathcal{D}}\max\\!\left(0,P(x)-Q(x)\right).$

Given two distributions $P$ and $Q$ over a finite domain $\mathcal{D}$, how
hard is it to compute $d_{\mathrm{TV}}(P,Q)$? If $P$ and $Q$ are explicitly
specified by the probabilities of all of the points of the (discrete) domain
$\mathcal{D}$, summing up the absolute values of the differences in
probabilities at all points leads to a simple linear time algorithm. However,
in many applications, the distributions of interest are of a high dimension
with succinct representations. In these scenarios, since the size of the
domain $\mathcal{D}$ is exponentially large compared to its representation, an
$O(|\mathcal{D}|)$ algorithm is highly impractical. This leads to the
following fundamental computational question:

> How hard is it to compute TV distance for high dimensional distributions?

The simplest model for a high-dimensional distribution is the product
distribution, which is a product of independent Bernoulli distributions. Let a
Bernoulli distribution with parameter $p$ be denoted by
$\mathrm{Bern}\\!\left(p\right)$. A product distribution $P$ over
$\\{0,1\\}^{n}$ can be described by $n$ parameters $p_{1},\dots,p_{n}$ where
each $p_{i}\in[0,1]$ is the probability that the $i$-th coordinate equals $1$
(such a $P$ is usually denoted by $\bigotimes_{i=1}^{n}\mathrm{Bern}(p_{i})$).
For any $x\in\\{0,1\\}^{n}$, the probability of $x$ with respect to the
distribution $P$ is given by $P\\!\left(x\right)=\prod_{i\in
S}p_{i}\prod_{i\in\left[n\right]\setminus
S}\left(1-p_{i}\right)\in\left[0,1\right]$, where $S\subseteq\left[n\right]$
is such that $i\in S$ if and only if the $i$-th coordinate of $x$ is $1$,
independently.

We show that the exact computation of the total variation distance between two
product distributions $P$ and $Q$ is $\\#\mathsf{P}$-complete. This is a
surprising result, given that for many other distance measures such as
Hellinger, Chi-square, and Kullback–Leibler divergence, there are efficient
algorithms for computing the distance between two product distributions.

### Notation:

We use $\left[n\right]$ to denote the _ordered_ set
$\left\\{1,\dots,n\right\\}$ and $\log$ to denote $\log_{2}$. Moreover, we
shall assume that all probabilities are represented as rational numbers of the
form $a/b$.

##  2 The Hardness of Computing TV Distance

######  Theorem 1.

Given two product distributions $P$ and $Q$, computing $d_{\mathrm{TV}}(P,Q)$
is $\\#\mathsf{P}$-complete.

We first introduce a problem called $\\#\textsc{PMFEquals}$ and show that it
is $\\#\mathsf{P}$-hard. We have that $\\#\textsc{PMFEquals}$ is the following
problem: Given a probability vector $\left(p_{1},\dots,p_{n}\right)$ where
$p_{i}\in\left[0,1\right]$ and a number $v$, compute the number of
$x\in\left\\{0,1\right\\}^{n}$ such that $P\\!\left(x\right)=v$ (that is the
number $|\\{x\in\\{0,1\\}^{n}\mid P(x)=v\\}|$), where $P$ is the product
distribution described by $\left(p_{1},\dots,p_{n}\right)$.

######  Lemma 2.

$\\#\textsc{PMFEquals}$ is $\\#\mathsf{P}$-hard.

###### Proof.

We will show a reduction from $\\#\textsc{SubsetProd}$ to
$\\#\textsc{PMFEquals}$, and the result will follow from the fact that
$\\#\textsc{SubsetProd}$ is $\\#\mathsf{P}$-hard. $\\#\textsc{SubsetProd}$ is
the following problem: Given integers $a_{1},\dots,a_{n},T$, compute the
number of sets $S\subseteq\left[n\right]$ such that $\prod_{i\in S}a_{i}=T$.

Let $a_{1},\dots,a_{n}$, and $T$ be the numbers of an arbitrary
$\\#\textsc{SubsetProd}$ instance $I_{S}$. We will create a
$\\#\textsc{PMFEquals}$ instance $I_{P}$ that has the same number of solutions
as $I_{S}$. To this end, let $p_{i}:=\frac{{a_{i}}}{1+{a_{i}}}$ for every $i$
and $v:=T\prod_{i\in\left[n\right]}(1-p_{i})$, and observe that
$a_{i}=\frac{p_{i}}{1-p_{i}}$. For any set $S\subseteq[n]$, we have the
following equivalences:

$\prod_{i\in S}a_{i}=T\Leftrightarrow\prod_{i\in
S}\frac{p_{i}}{1-p_{i}}=\frac{v}{\prod_{i\in\left[n\right]}(1-p_{i})}\Leftrightarrow\prod_{i\in
S}p_{i}\prod_{i\notin S}\left(1-p_{i}\right)=v\Leftrightarrow
P\\!\left(x_{S}\right)=v,$

where $x_{S}$ is such that $x_{i}=1$ if and only if $i\in S$. This completes
the proof. ∎

We now turn to Theorem 1.

###### Proof of Theorem 1.

We separately prove membership in $\\#\mathsf{P}$ and
$\\#\mathsf{P}$-hardness.

### Membership in $\\#\mathsf{P}$:

Let $P$ and $Q$ be two product distributions specified by $p_{1},\dots,p_{n}$
and $q_{1},\dots,q_{n}$, respectively. Without loss of generality we shall
assume that these parameters are fractions (as we only have some finite
precision available). The goal is to design a nondeterministic machine ${\cal
N}$ that takes $p_{1},\dots,p_{n}$ and $q_{1},\dots,q_{n}$ as inputs and is
such that the number of its accepting paths (normalized by an appropriate
quantity) equals $d_{\mathrm{TV}}(P,Q)$.

Let $M$ be the product of the denominators of all parameters
$p_{1},\dots,p_{n},q_{1},\dots,q_{n}$ and their complements
$1-p_{1},\dots,1-p_{n},1-q_{1},\dots,1-q_{n}$. The non-deterministic machine
${\cal N}$ first guesses an element $i\in\left\\{0,1\right\\}^{n}$ in the
sample space of $P$ and $Q$, computes $|P(i)-Q(i)|$ by using the parameters
$p_{1},\dots,p_{n},q_{1},\dots,q_{n}$, then guesses an integer $0\leq z\leq
M$, and finally accepts if and only if $1\leq z\leq M|P(i)-Q(i)|$. (Note that
$M|P(i)-Q(i)|=\left|M\cdot P(i)-M\cdot Q(i)\right|$ is an integer.)

It follows that
$d_{\mathrm{TV}}(P,Q)=\frac{1}{2}\sum_{i\in\left\\{0,1\right\\}^{n}}\left|P\\!\left(i\right)-Q\\!\left(i\right)\right|$
is equal to the number of accepting paths of ${\cal N}$ divided by ${2M}$.

###  $\\#\mathsf{P}$-hardness:

For establishing hardness, we will show a reduction from
$\\#\textsc{PMFEquals}$ to computing TV distance between product
distributions. The theorem will then follow from Lemma 2.

Let $p_{1},\dots,p_{n}$ and $v$ be the numbers in an arbitrary instance of
$\\#\textsc{PMFEquals}$ where each $p_{i}$ is represented as an $m$-bit binary
fraction. With this, $P(x)$ can be represented as an $nm$-bit binary fraction.
Thus without loss of generality, we can assume that $v$ is also an $nm$-bit
fraction. We distinguish between two cases depending on whether $v<2^{-n}$ or
$v\geq 2^{-n}$.

#### Case A: $v<2^{-n}$.

First, we construct two distributions
$\hat{P}=\mathrm{Bern}\\!\left(\hat{p}_{1}\right)\otimes\cdots\otimes\mathrm{Bern}\\!\left(\hat{p}_{n+1}\right)$
and
$\hat{Q}=\mathrm{Bern}\\!\left(\hat{q}_{1}\right)\otimes\cdots\otimes\mathrm{Bern}\\!\left(\hat{q}_{n+1}\right)$
over $\\{0,1\\}^{n+1}$ as follows: $\hat{p}_{i}:=p_{i}$ for
$i\in\left[n\right]$ and $\hat{p}_{n+1}:=1$; $\hat{q}_{i}:=1/2$ for
$i\in\left[n\right]$ and $\hat{q}_{n+1}:=v2^{n}$. We have that
$d_{\mathrm{TV}}\\!\left(\hat{P},\hat{Q}\right)$ is, by definition, equal to
the sum
$\sum_{x\in\\{0,1\\}^{n+1}}\max\\!\left(0,\hat{P}\\!\left(x\right)-\hat{Q}\\!\left(x\right)\right)$
or

$\displaystyle\sum_{x\in\left\\{0,1\right\\}^{n}}\max\\!\left(0,P\\!\left(x\right)-\frac{1}{2^{n}}v2^{n}\right)=\sum_{x\in\left\\{0,1\right\\}^{n}}\max\\!\left(0,P\\!\left(x\right)-v\right)=\sum_{x:P\left(x\right)>v}\left(P\\!\left(x\right)-v\right).$
(1)

We define two more distributions $P^{\prime}$ and $Q^{\prime}$ over
$\\{0,1\\}^{n+2}$, by making use of the following claim.

######  Claim 3.

For $\beta=\frac{1}{2^{3nm}}$, the following hold for all $x$: If
$P\\!\left(x\right)<v$, then
$P\\!\left(x\right)\left(\frac{1}{2}+\beta\right)<v\left(\frac{1}{2}-\beta\right)$;
if $P\\!\left(x\right)>v$, then
$P\\!\left(x\right)\left(\frac{1}{2}-\beta\right)>v\left(\frac{1}{2}+\beta\right)$.

###### Proof.

For 3 to hold, observe that we want $\beta$ to be at most
$\frac{|v-P(x)|}{v+P(x)}$ for every $x$, so that $P(x)\neq v$. Since both $v$
and $P(x)$ have $nm$-bit representations, both $|v-P(x))|$ and $v+P(x)$ have
$nm$-bit representations. Thus $\frac{|v-P(x)|}{v+P(x)}$ can be represented as
a $2nm$-bit fraction. Since this fraction is not zero, and the smallest
$2nm$-bit fraction is $\frac{1}{2^{2nm}}$, choosing $\beta:=\frac{1}{2^{3nm}}$
suffices. ∎

We now define $P^{\prime}$ and $Q^{\prime}$ as follows:
$p_{i}^{\prime}:=p_{i}$ for $i\in[n]$, $p_{n+1}^{\prime}:=1$, and
$p_{n+2}^{\prime}:=\frac{1}{2}+\beta$; $q_{i}^{\prime}:=\frac{1}{2}$ for
$i\in[n]$, $q_{n+1}^{\prime}:=v2^{n}$, and
$q_{n+2}^{\prime}:=\frac{1}{2}-\beta$ where $\beta$ is as in 3. We establish
the following.

######  Claim 4.

We have that $\left|\left\\{x\mid
P\\!\left(x\right)=v\right\\}\right|=\frac{1}{2\beta
v}\left(d_{\mathrm{TV}}\\!\left(P^{\prime},Q^{\prime}\right)-d_{\mathrm{TV}}\\!\left(\hat{P},\hat{Q}\right)\right)$.

###### Proof.

We have that $d_{\mathrm{TV}}\\!\left(P^{\prime},Q^{\prime}\right)$ is equal
to
$\sum_{x\in\\{0,1\\}^{n+2}}\max\\!\left(0,P^{\prime}\\!\left(x\right)-Q^{\prime}\\!\left(x\right)\right)$
or

$\displaystyle\sum_{x\in\\{0,1\\}^{n}}\max\\!\left(0,P\\!\left(x\right)\left(\frac{1}{2}+\beta\right)-\frac{v2^{n}}{2^{n}}\left(\frac{1}{2}-\beta\right)\right)+\max\\!\left(0,P\\!\left(x\right)\left(\frac{1}{2}-\beta\right)-\frac{v2^{n}}{2^{n}}\left(\frac{1}{2}+\beta\right)\right)$
$\displaystyle=\sum_{x}\max\\!\left(0,P\\!\left(x\right)\left(\frac{1}{2}+\beta\right)-v\left(\frac{1}{2}-\beta\right)\right)+\max\\!\left(0,P\\!\left(x\right)\left(\frac{1}{2}-\beta\right)-v\left(\frac{1}{2}+\beta\right)\right)$
$\displaystyle=\sum_{x:P\left(x\right)\geq
v}P\\!\left(x\right)\left(\frac{1}{2}+\beta\right)-v\left(\frac{1}{2}-\beta\right)+\sum_{x:P\left(x\right)>v}P\\!\left(x\right)\left(\frac{1}{2}-\beta\right)-v\left(\frac{1}{2}+\beta\right)$
$\displaystyle=\sum_{x:P\left(x\right)=v}P\\!\left(x\right)\left(\frac{1}{2}+\beta\right)-v\left(\frac{1}{2}-\beta\right)+\sum_{x:P\left(x\right)>v}P\\!\left(x\right)\left(\frac{1}{2}+\beta\right)-v\left(\frac{1}{2}-\beta\right)$
$\displaystyle\qquad+\sum_{x:P\left(x\right)>v}P\\!\left(x\right)\left(\frac{1}{2}-\beta\right)-v\left(\frac{1}{2}+\beta\right)=2\beta
v\left|\left\\{x\mid
P\\!\left(x\right)=v\right\\}\right|+\sum_{x:P\left(x\right)>v}\left(P\\!\left(x\right)-v\right).$

The result now follows from Equation 1. The first equality above follows from
the definitions of $P^{\prime}$ and $Q^{\prime}$ (since $p_{n+1}^{\prime}=1$).
Note that for every $x$ with $P(x)<v$, by Claim 3,
$P(x)(\frac{1}{2}+\beta)<v(\frac{1}{2}-\beta)$ and if $P(x)\geq v$, then
$P(x)(\frac{1}{2}+\beta)\geq v(\frac{1}{2}-\beta)$. Also when $P(x)\leq v$, we
have that $P(x)(\frac{1}{2}+\beta)$ is at most $v(\frac{1}{2}-\beta)$ and when
$P(x)>v$, by Claim 3, we have $P(x)(\frac{1}{2}-\beta)>v(\frac{1}{2}+\beta)$.
These imply the second equality. The rest of the equalities hold by algebraic
manipulations. ∎

Thus, $|\\{x\mid P(x)=v\\}|$ can be computed by computing
$d_{\mathrm{TV}}(P^{\prime},Q^{\prime})$ and
$d_{\mathrm{TV}}(\hat{P},\hat{Q})$. Thus the proof in this case follows by
Lemma 2.

#### Case B: $v\geq 2^{-n}$.

First, let us define distributions
$\hat{P}=\mathrm{Bern}\\!\left(\hat{p}_{1}\right)\otimes\cdots\otimes\mathrm{Bern}\\!\left(\hat{p}_{n}\right)$
and
$\hat{Q}=\mathrm{Bern}\\!\left(\hat{q}_{1}\right)\otimes\cdots\otimes\mathrm{Bern}\\!\left(\hat{q}_{n}\right)$
as follows: $\hat{p}_{i}:=p_{i}$ for $i\in\left[n\right]$ and
$\hat{p}_{n+1}:=\frac{1}{v2^{n}}$; $\hat{q}_{i}:=\frac{1}{2}$ for
$i\in\left[n\right]$ and $\hat{q}_{n+1}:=1$.

We now have that $d_{\mathrm{TV}}\\!\left(\hat{P},\hat{Q}\right)$ is equal to
$\frac{1}{2}\sum_{x}\left|\hat{P}\\!\left(x\right)-\hat{Q}\\!\left(x\right)\right|$
or

$\displaystyle\sum_{x}\max\\!\left(0,\hat{P}\\!\left(x\right)-\hat{Q}\\!\left(x\right)\right)$
$\displaystyle=\sum_{x}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}-\frac{1}{2^{n}}\right)+\sum_{x}\max\\!\left(0,P\\!\left(x\right)\left(1-\frac{1}{v2^{n}}\right)\right)$
$\displaystyle=\sum_{x}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}-\frac{1}{2^{n}}\right)+1-\frac{1}{v2^{n}}.$

As earlier, we define two more distributions $P^{\prime}$ and $Q^{\prime}$, by
making use of 3. The new distributions $P^{\prime}$ and $Q^{\prime}$ are such
that $p_{i}^{\prime}:=p_{i}$ for $i\in\left[n\right]$,
$p_{n+1}^{\prime}:=\frac{1}{v2^{n}}$, and
$p_{n+2}^{\prime}:=\frac{1}{2}+\beta$; $q_{i}^{\prime}:=1/2$ for
$i\in\left[n\right]$, $q_{n+1}^{\prime}:=1$, and
$q_{n+2}^{\prime}:=\frac{1}{2}-\beta$. We establish the following claim.

######  Claim 5.

We have that $\left|\left\\{x\mid
P\\!\left(x\right)=v\right\\}\right|=\frac{2^{n-1}}{\beta}\left(d_{\mathrm{TV}}\\!\left(P^{\prime},Q^{\prime}\right)-d_{\mathrm{TV}}\\!\left(\hat{P},\hat{Q}\right)\right)$.

###### Proof.

We have that $d_{\mathrm{TV}}\\!\left(P^{\prime},Q^{\prime}\right)$ is equal
to
$\sum_{x}\max\\!\left(0,P^{\prime}\\!\left(x\right)-Q^{\prime}\\!\left(x\right)\right)$
or

$\displaystyle\sum_{x}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}+\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}-\beta\right)\right)+\max\\!\left(\\!0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}-\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}+\beta\right)\right)$
$\displaystyle\qquad+\sum_{x}\max\\!\left(0,P\\!\left(x\right)\left(1-\frac{1}{v2^{n}}\right)\left(\frac{1}{2}+\beta\right)\right)+\max\\!\left(0,P\\!\left(x\right)\left(1-\frac{1}{v2^{n}}\right)\left(\frac{1}{2}-\beta\right)\right)$
$\displaystyle=\sum_{x}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}+\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}-\beta\right)\right)$
$\displaystyle\qquad+\sum_{x}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}-\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}+\beta\right)\right)+\max\\!\left(0,P\\!\left(x\right)\left(1-\frac{1}{v2^{n}}\right)\right).$

Applying 3, we have that
$d_{\mathrm{TV}}\\!\left(P^{\prime},Q^{\prime}\right)$ is equal to

$\displaystyle\sum_{x:P\left(x\right)\geq
v}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}+\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}-\beta\right)\right)$
$\displaystyle\qquad+\sum_{x:P\left(x\right)>v}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}-\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}+\beta\right)\right)+1-\frac{1}{v2^{n}}$
$\displaystyle=\sum_{x:P\left(x\right)=v}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}+\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}-\beta\right)\right)$
$\displaystyle\qquad+\sum_{x:P\left(x\right)>v}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}+\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}-\beta\right)\right)$
$\displaystyle\qquad+\sum_{x:P\left(x\right)>v}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}\left(\frac{1}{2}-\beta\right)-\frac{1}{2^{n}}\left(\frac{1}{2}+\beta\right)\right)+1-\frac{1}{v2^{n}}$
$\displaystyle=2\beta\frac{1}{2^{n}}\left|\left\\{x\mid
P\\!\left(x\right)=v\right\\}\right|+\sum_{x}\max\\!\left(0,P\\!\left(x\right)\frac{1}{v2^{n}}-\frac{1}{2^{n}}\right)+1-\frac{1}{v2^{n}}$
$\displaystyle=\frac{\beta}{2^{n-1}}\left|\left\\{x\mid
P\\!\left(x\right)=v\right\\}\right|+d_{\mathrm{TV}}\\!\left(\hat{P},\hat{Q}\right).$

This concludes the proof. ∎

Thus, also in this case, the proof follows by Lemma 2. ∎

##  3 Bibliographical Remarks

[SV03] established, in a seminal work, that additively approximating the TV
distance between two distributions that are samplable by Boolean circuits is
hard for $\mathsf{SZK}$. Subsequent works captured variations of this theme
[GSV99, Mal15, DGPV20]: For example, [GSV99] showed that the problem of
deciding whether a distribution samplable by a Boolean circuit is close or far
from the uniform distribution is complete for $\mathsf{NISZK}$. Finally,
[CMR07, LP02, Kie18] show that it is undecidable to check whether the TV
distance between two hidden Markov models is greater than a threshold or not,
and that it is $\\#\mathsf{P}$-hard to additively approximate it.

On an algorithmic note, [BGMV20] designed efficient algorithms to additively
approximate the TV distance between distributions efficiently samplable and
efficiently computable. In a similar vein, [PM21] studied a related _property
testing_ variant of TV distance for distributions encoded by circuits.
Recently, [FGJW23] designed an FPRAS for relatively approximating the TV
distance between two arbitrary product distributions and [FLL24] gave an FPTAS
for it.

### Acknowledgements:

This work was supported in part by the National Research Foundation Singapore
under its NRF Fellowship Programme [NRF-NRFFAI-2019-0002, NRF-
NRFFAI1-2019-0004], Amazon Faculty Research Awards, an initiation grant by IIT
Kanpur (SG), SERB award CRG/2022/007985 (SG), and NSF awards 2130536 and
2130608. This work was done in part when AB, DM, AP, and NVV visited the
Simons Institute for the Theory of Computing.

## References

  * [BGM+23] Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinodchandran.  On approximating total variation distance.  In Proc. of IJCAI, 2023.
  * [BGMV20] Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, and N. V. Vinodchandran.  Efficient distance approximation for structured high-dimensional distributions via learning.  In Proc. of NeurIPS, 2020.
  * [CMR07] Corinna Cortes, Mehryar Mohri, and Ashish Rastogi.  ${L}_{p}$ distance and equivalence of probabilistic automata.  Int. J. Found. Comput. Sci., 18(4):761–779, 2007.
  * [DGPV20] Peter Dixon, Sutanu Gayen, Aduri Pavan, and N. V. Vinodchandran.  Perfect zero knowledge: New upperbounds and relativized separations.  In Proc. of TCC, 2020.
  * [FGJW23] Weiming Feng, Heng Guo, Mark Jerrum, and Jiaheng Wang.  A simple polynomial-time approximation algorithm for the total variation distance between two product distributions.  TheoretiCS, 2, 2023.
  * [FLL24] Weiming Feng, Liqiang Liu, and Tianren Liu.  On deterministically approximating total variation distance.  In David P. Woodruff, editor, Proc. of SODA, 2024.
  * [GSV99] Oded Goldreich, Amit Sahai, and Salil P. Vadhan.  Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK.  In Proc. of CRYPTO, 1999.
  * [Kie18] Stefan Kiefer.  On computing the total variation distance of hidden Markov models.  In Proc. of ICALP, 2018.
  * [LP02] Rune B. Lyngsø and Christian N. S. Pedersen.  The consensus string problem and the complexity of comparing hidden Markov models.  J. Comput. Syst. Sci., 65(3):545–569, 2002.
  * [Mal15] Lior Malka.  How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge.  J. Cryptol., 28(3):533–550, 2015.
  * [PM21] Yash Pote and Kuldeep S. Meel.  Testing probabilistic circuits.  In Proc. of NeurIPS, 2021.
  * [SV03] Amit Sahai and Salil P. Vadhan.  A complete problem for statistical zero knowledge.  J. ACM, 50(2):196–249, 2003.