Computational Explorations of Total Variation Distance
Authors: Arnab Bhattacharyya
Sutanu Gayen
Kuldeep S. Meel
Dimitrios Myrisiotis
A. Pavan
N. V. Vinodchandran
Venue: ICLR 2025 Spotlight (2025)
Keywords: total variation distance
TV distance
mixtures of products
equivalence checking
Ising models
computational complexity
FPRAS
Primary area: learning theory

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.

Published as a conference paper at ICLR 2025
COMPUTATIONAL EXPLORATIONS OF TOTAL VARIA- TION DISTANCE
Arnab Bhattacharyya' University of Warwick
Sutanu Gayen ITT Kanpur
Kuldeep S. Meel
University of Toronto Georgia Institute of Technology
Dimitrios Myrisiotis CNRS@CREATE LTD.
A. Pavan Iowa State University
N. V. Vinodchandran
University of Nebraska-Lincoln
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 zero. Second, we prove that unless NP C RP it is impossible to efficiently estimate the TVV distance between arbitrary Ising models, even in a bounded-eree -eroor randomized setting.
INTRODUCTION
The total variation (TV) distance between distributions P and Q over a common sample space D, denoted by dTv Q), ) defined as
drv Q) max ((S)) - = Σ - Σ max(0, - Q(x)). SED
sED
The TV distance satisfies many basic properties which makes it a versatile and fundamental measure for quantifying the dissimilarity between probability distributions. First, has an explicit probabilistic interpretation: The TV distance between two distributions is the maximum gap between the proba- bilities assigned to a single event by the two distributions. Second, it satisfies many mathematically desirable properties: It is bounded and lies in [0, 1j. it is metric, and it is invariant with respect to bi- jections. Third, satisfies some interesting composability property. Given f(11, ....... .n). suppose replace 92 with 922 such that drv g/) < s. Then the TV distance between f(1 f2 ......... 9n)
and /991.92.-. 9n) is at most &. Because of these reasons, the total variation distance a central distance measure employed in wide range of areas including probability and statisties Mitzen macher & Upfal (2005), machine learning Shalev-Shwartz & Ben-David (2014), and information theory Cover & Thomas (2006), cryptography Stinson (1995), data privacy Dwork 2006), and pseudorandomness Vadhan (012)).
Lately, the computational aspects of TV distance have attracted lot of attention. Sahai Vadhan (003) established, in a seminal work, that additively approximating the TV distance between two distributions that are samplable by Boolean circuits is hard for SZK (Statistical Zero Knowledge).
The complexity class SZK is fundamental to cryptography and is believed to be computationally hard. Subsequent works captured variations of this theme Goldreich et (1999); Malka| (2015): Dixon al. (2020): For example, Goldreich et al. (1999) showed that the problem of deciding whether distribution samplable by a Boolean circuit is close or far from the uniform distribution is complete for NISZK (Non- Interratrtt Statistical Zero Knowledge). Moreover, Cortes et al.) (207)); Lyngse & Pedersen (2002); Kiefer (2018) showed that it is undecidable to check whether the TV distance between two hidden Markov models is greater than threshold or not, and that it is #--hard to additively approximate it. Finally, |Bhattacharyya et al. (023) showed that (a) exactly computing the
Work done while the author was liate with the National University of Singapore.

---

Published as a conference paper at ICLR 2025
TV distance between product distributions is #P-complete, and (6) multiplicatively approximating the TV distance between Bayes nets is NP-hard.
On an algorithmic note, Bhattacharyya al. (2020) designed efficient algorithms to additively ap- proximate the TV distance between distributions efficiently samplable and efficiently computable (including the case of ferromagnetic Ising models). In partieular, they designed efficient algorithms for additively approximating the TV distance of structured high dimensional distributions such as Bayesian networks, Ising models, and multivariate Gaussians. In a similar vein, Pote & Meel (202T) studied related property testing variant of TV distance for distributions encoded by circuits. Multiplicative approximation of TV distance has received less attention compared to additive ap- proximation. Recently, |Bhattacharyya et al. (2023) gave an FPTAS for estimating the TV distance between an arbitrary product distribution and product distribution with bounded number of distinct marginals. Feng et al. (2023) designed an FPRAS for multiplicativel approximating the TV distance between two arbitrary product distributions and Feng al. (2024) gave an FPTAS for the same task. Finally, Bhattacharyya et al. (2024) gave FPRAS for estimating the TV distance between Bayes nets of small treewidth.
In this paper we address some previously unexplored (or under-explored) computational aspects of total variation distance relating to mixtures of product distributions and Ising models.
1.1 EQUIVALENCE CHECKING FOR MIXTURES OF PRODUCT DISTRIBUTIONS
Mixtures of product distributions constitute natural and important class of distributions that have been studied in the mathematics and computer science literature. For instance, it is a standard observation that any distribution can be described by some (possibly large) mixture of product distributions (see Observation 9 in Appendix A).
Freund & Mansour (1999) gave an efficient algorithm for learning mixture of two product distribu- tions over the Boolean domain. As part of their analysis, they showed that given two mixtures of two product distributions, their KL divergence can be upper bounded by that of the components and certain distance between the mixture coefficients. However, this upper bound does not lead to an equivalence checking algorithm.
A related problem in machine learning is source identification, whereby one is asked to identify the source parameters of a distribution. Gordon et al. (202I); Gordon & Schulman (2022); Gordon et al.) (2023) give algorithms for source identification of mixture of k product distributions bits, when given as input approximate values of multilinear moments.
We focus the equivalence checking problem regarding mixtures of product distributions. Note that while it is easy to check whether two product distributions are equivalent, that is, by checking whether their respective Bernoulii parameters product distributions. This is so, because there are mixtures of product distributions that are equal (as distributions) but different sets of Bernoulli parameters describe them. For example, consider the case where we have two mixtures over one bit, namely P = 1 P1 + 0- P2 and Q = 2 Q + + Q2, where Pi = Pg Bern( H) while Q = Bern( 1)) and Q2 = Bern (3) In this case, P = Q = Bern ) but the parameters of P and Q are different.
equal, it is not clear how do so for the case of mixtures of
We present a simple deterministic polynomial-time algorithm for checking equivalence between mixtures of product distributions. Let us first formally define mixtures of product distributions, Let
W1,- ,.,.... We be real numbers (weights) such that 0 < w; S for all 1 < S k, Σ w; = 1, and Pt, Pi,..., Ps n--dimensional product distributions over alphabet Σ. The distribution P specified by the tuple (Wi,..., Wk: Pi,..., Pk) is a mixture of products if for all x E Σn it is the case that P(x) - (x). For distribution P, we denote by pSi its marginal on the first i variables. We may now state our first main result.
Theorem 1. There a deterministic algorithm E such that, given two mixtures of product distri- butions P and Q, specified by (wi...., Wk. Pı..... Pk) and (UI...., Uk, Q....., Qk), respectively, decides whether = Q or not. Moreover, if P + Q, then oulputs some x E Di (with i S that (z)(2) + (x)) The running time of E is O(nk' ()
such such
(Note that the algorithm outlined in Theorem I has input size 2kk (EI).) The primary conceptual contribution of our work is connection between equivalence checking for mixtures of distributions
2

---

Published as a conference paper at ICLR 2025
and basis construction over appropriately chosen vector space. The connection lends itself to construction that makes the algorithm as well as proof accessible to undergraduates.
1.2 HARDNESS OF APPROXIMATING TOTAL VARIATION DISTANCE BETWEEN ISING MODELS
The Ising model Ising T925| Lenz 1920), originally developed to describe ferromagnetism in statistical mechanies, serves comnersoon in the study of phase transitions and critical phenomena. consists of discrete variables, known as spins, which can take values either +1 or -1. These spins are arranged on lattice, and their interactions with nearest neighbors lead to rich tapestry of behavior, including spontaneous magnetization and phase transitions at critical temperatures.
One of the most fascinating aspects of the Ising model is its ability to illustrate complex systems using simple rules. For instance, in 2D, it exhibits a second-order phase transition at a critical temperature, where the system changes from disordered state to ordered state temperature decreases. This model has been extensively studied, leading to profound insights not only in physics but also in fields such as biology, sociology, and computer science. For more information the reader invited to check the survey written by Cipra (1987).
On another note, the computational study of the Ising model has become increasingly relevant. With its relatively simple structure arructure-interacting binary spins on lattice, the Ising model serves as an ideal platform for exploring computational techniques ranging from Monte Carlo simulations to mean-field approximations. Monte Carlo methods, in particular, are widely used to investigate thermodynamic properties of the Ising model, as they allow for efficient sampling of spin configurations at various temperatures, enabling the computation of quantities like magnetization and susceptibility.
Some notable algorithmic results along these lines are the ones by Kasteleyn (1963) and Fisher (1966), whereby they showed that the evaluation of the partition function for planar Ising models can be reduced to some appropriate determinant computations. Moreover, Jerrum & Sinclair (1933) devised an efficient Monte Carlo approximation algorithm for estimating the partition function of arbitrary ferromagnetic (whereby all wa.ys 's are positive) Ising models.
On the other hand, there are some works pertaining to the intractability of computing various quantities of interest regarding Ising models (Welsh] 1993), such as the partition function outlined above. For example, Jerrum & Sinclair (1993) show that unless NP RP, there is no fully polynomial-time randomized approximation scheme (FPRAS) to estimate the partition function of arbitrary Ising models. Moreover, Istrail (2000) proves that computing the partition function (for various kinds of Ising models) is NP-complete.
The second part of our work falls this latter category. Let us first fix some notation. We focus on Ising models P such that for all E {f- {-1, 1}" " it is the case that the probability that the underlying system of spins assumes the configuration x is
P(x) = Z exp
Σ 1
Wa. + Chas hias o exp
Σ Wiiysay Σ hira
whereby Z :: Eg exp Ei, wiyy + E, heg)) is the partition function of P. and {wis Jig and {hr), are the parameters of the system.
We prove that it is hard to estimate the TV distance between Ising models under the very mild complexity-theoreet assumption NP g RP, which states that Boolean formula satisfiability (SAT) does not admit any one-sided-error randomized polynomial-time algorithm, that is, randomized polynomial-time algorithm that may output a false positive answer with small probability (Arora & Barak 2009).
Theorem 2. NP g RP, then there is FPRAS that estimates the TV distance between any two Ising models.
Our proof draws on the hardness result of JJerumm& & Sinclair (199)). and shows that the partition function of Ising models can be reduced to the TV distance between Ising models, by simple efficient approximation preserving reduction. The main ingredients of this reduction are as follows. First, prove that estimating the partition function of any Ising model reduces to estimating any atomic
3

---

Published as a conference paper at ICLR 2025
marginal the form Pry(r,- =1] for any variable æ4 and any Ising model P (see Proposition 6). Then we show that estimating any atomic marginal the form Pry(z, = =1 for any variable 24 and any Ising model P, can be reduced to estimating the TV distance between the Ising models P. Q. whereby Q depends on P (see Proposition 7
1.3 PAPER ORGANIZATION
We give some preliminaries in Section 2
We prove Theorem in Section and Theorem 2 in Section 4 We conclude in /Section 5 with some interesting open problems, Observation 9 is proved in Appendix (ropossiinn 6 proved in Appendix
PRELIMINARIES
We require the following folklore result, which is an application of Gaussian elimination.
Proposition 3. There is deterministic algorithm G that gets input set of vectors V, and outpuis
a maximum- size subset S S V of linearly independent vectors. The running time of G is O (vi').
An n-dimensional product distribution I over an alphabet Σ is described by the n |>]] parameters
Pr
ke(m). fiEn) vEΣ
so that
R(x) = II
Pr = x;] for all x E E". i=1 R
R
For n-dimensional product distribution over an alphabet E, we denote its marginal over the first
1 S j S n coordinates by RSI. Note that for any x E y we have (r) = IP Pra[X; = xi).
We shall also require the following notion of approximation algorithm.
Definition 4. A function f 10, " + R admits a fully polynomial-tine randomized approximation scheme (FPRAS) if there is a randomized algorithm such that for every input x (of length n)) and parameters 6 >>0 O, the algorithm A outputs a e-multipliaative approximation of fxx), i.e., a value
that lies in the interval [f (11)/(1+ + E), (1 + (x)), with probability at least 8. The running time of A is polynomial in 1/1, 1/5.
3 EQUIVALENCE CHECKING FOR MIXTURES OF PRODUCT DISTRIBUTIONS
Let us now prove Theorem First, observe that P Q if and only if PS/ Q for all 1 S S This so, since if Q, then every marginal of matches the respective marginal of Q (in symbols, PSi QSi for all 1 < n)). Otherwise, there would be some 1 I j such that pSi (y) * Q (y). The latter would then establish the existence of an x == (y, 2) E ""
and y Σ
(for some "² such that P(x) # Q(x). On the other hand, if pši Q for all 1 S j $ n, then psn Q which in particular implies that P = Q.
Note that the condition PSJ Q for all 1 S j S n is equivalent, by the definitions of P and Q, to the condition Σ w.P. W.P.S. Dk 1 1 S n so that E w.P.s E $Q
Dis 2.O.s) for all s j S n. Thus, if P + Q, then there some
We will use an inductive argument on 1 < S to show that these conditions can be efficiently checked (in either case).
Base Case. For j we can efficiently check whether is the case that
w.P.P Σ
This is done by checking for all x E Σ that
k
Σ
w. Xr
= x|
Σ
U/
Pr[X, =
=
p.
Q
1=1
4

---

Published as a conference paper at ICLR 2025
If these tests pass, then the algorithm proceeds with the inductive argument outlined below (otherwise, outputs z). Towards this, we will now find a basis B1 for the set of coefficient vectors of the equations
Pr(X1 = x] Σ 2 Pr[X1 x] 2k++ 0
xEW
over variables 21,..., 222. Note that the size of B1 is at most min, (-]]] I 2k. We can find B1 as follows. We appeal to Proposition 3 and run the algorithm G outlined there the set of vectors
(w1 Pr(Xx 20
Pr[X1 21 =1)} MET
we Pr[X1 2)
Pr[X1 x
Uh
Qx
(in time 0 ( Then, we define B1 to be the set of independent vectors being output by G.
Induction Hypothesis.
Assume that for a j 2 1 the case that
k
w
and we have a basis B, for the set of coefficient vectors of the following equations
w.P p. (I)
Σ u0 (x) zkti 0
xEΣ
over variables 21...., 22k. Note that B, is of size at most min (2k: 2D)) < 2k.
Induction Step. We will establish that we can check whether P and Q agree up coordinate + 1 and compute a basis B for the respective set of coefficient vectors of the equations that capture this equivalence.
To see whether P' and Q agree up to coordinate j + 1, one needs to check that
Σ w. P.
( (x) (r)))r((-))))) 1-1 v) Σ Q (1) Pr(X pr( = 00
for all æ E > and y Σ. A crucial observation (that follows from the inductive hypothesis) that we only need to check whether these equations hold for the assignments x that correspond to vectors in By, and the values y E (Note that each basis vector E B, can be specified by an assignment rr D' This follows from the way these basis vectors are constructed. See below, the discussion after Claim 5) If any of these tests fails, then the algorithm outputs (I, y); else, it continues as follows.
To proceed with the induction, it would suffice to show how to construct basis Bj41 for the set of coefficient vectors of the following equations over variables 21,..., 22k, namely
w. P.P.S SS (x) Pr = = 24
(x)
= =x =
P.
Q
WEE
Let B, = (b, = (b........ b1,55) ....,,,. = (bm,l.... b whereby m S 2k and C' :
U C. is such that
{ Pr[X = = .i....,,,,r. Pr(X x+ y]
C =
Ph
b Pr[X = v) ..... b1,28 Pr(Xf+1 = v) yEr.
Q
Q
5

---

Published as a conference paper at ICLR 2025
{mmi (mmi Pr[X 1mm.Pr(Xst+ = y..., bm, Pr[X]+1 = 3/1
Om ==
Ph
bm,+1 Pr(X,+1 = y) ...., 22. Pr[X = v1)
Q:
Q
yEE
We require the following claim. Below, we denote the dot product of vectors b E I2 by (a, That is, (a, b) = -i== a,b;. Claim 5. It is the case that Bj+1 C.
Claim 5 helps explain how, for any vector E By+1. one may extract an assignment zy E Di that corresponds to b. This is done by keeping track of the Bernoulli parameters that appear in b: There is exactly one such parameter for each variable, and it refers to a symbol in Σ.
Proof of Claim 5
Let y E E. We have that
wi P (Ir 2 E SuQ (x, Zkti
wi p (x) Pr|X
02 Q (z) Pr| = =y- #kts.
Let := ( 224). By the inductive hypothesis, for any x E Y
Σ W (x) Σ
2n (x) zkti
can be written linear combination of {(be, 2) >) Concretely, there exist di....,, dm R such that
Σ w. P.PP (x) (x)
(1) Σ de (be, z).
Since the corresponding coefficients of each 2; must be equal between the LHS and the RHS of this equation, we get that for all <ii k.
Wc PSi (x)
de be,
and
Σ
de
beRts
8=1
t=1
for some d1, ....... dm. Then it is straightforward to see that for every E
&
w. PS' (2) Pr = =
wy 22
2441
Σ de (ce, 2) 1=1
P.
Q.
whereby eg is the vector within the set C3 that corresponds to the setting where Xj+1 = y. To see why this equation holds, will consider the coefficients of each in either side of this equation and show that they are equal. Let us consider the case where I S (The case where & + < i < 24 is similar.) In the LHS, the coefficient of 2; is equal to
m
w.P w.P.S. (x) 5 = vl = Σ
de b Pr[X = y)
P.
P.
by Equation (1) while the RHS it is equal to
Σ deccce ce, = Σ de bes Pr[X y],
P.
1=
by the definition of cz. This shows that By+1 is a subset C, and the proof is complete.
By Claim 5
O vectors. However, not all of these OTk (EI) vectors are (necessarily) independent. By Proposition 3 we can find the (at most) 2k
have that Bj+1 contains (at most) Σ
independent vectors among the O [-]) vectors in time 0 6- Σ
These vectors constitute B,+1-
This concludes the inductive description of algorithm.

---

Published as a conference paper at ICLR 2025
Running Time. Let (n,, k, Σ) denote the running time of this procedure, mixtures of size over n variables that have alphabet Σ. We have the recurrence relation
T(n, k. 23) - T( 1,K, 0A** 121
which in particular yields T(n, k Σ) = (nk* nk** )
4 HARDNESS OF APPROXIMATING TOTAL VARIATION DISTANCE BETWEEN ISING MODELS
In this section we prove Theorem
4.1 REDUCING THE PARTITION FUNCTION ATOMIC MARGINALS
We first observe the following. The proof is standard and is given in Appendix B
Proposition 6. If there is some FPRAS that estimates any atomic marginal of any Ising model P. namely Pry(zz = for any variable The then there is some FPRAS that estimates the partition function of any Ising model.
4.2 REDUCING THE ATOMIC MARGINALS TO TV DISTANCE
We prove the following.
Proposition 7. If there is some FPRAS that estimates the TV distance between any two Ising models, then there is some FPRAS that estimates any atomic marginal of any Ising model P, namely Prp(#t = for any variable Ft.-
Proof. Assume that there is some FPRAS that estimates the TV distance between any two Ising models. We will show that there is some FPRAS that estimates the atomic marginals of any Ising model P, namely Pr FPTAS that estimates the atomic marginals of any Ising model P.
11] for any variable
Let be the desired accuracy error of the
Fix some Ising model P with parameters (waghe, and {h4).. We shall first introduce new dummy variable 25. Let Po be new Ising model .o...-. . Fn with parameters {wa.hh. and (hx); that Wo,; = 0 for all 0 and ho + oo (that is, ho a small negative quantity which we will fix later). Note that under these conditions is independent from every other node 2 21..... En- Moreover,
Ex:r== exp
En Wi, E, h4Tz)
Pr(co- = 1| Pg
Σ am:20
Pa(x)
Σ. exp Ei, Wi.j + E, los2rs
Σ -= exp En, Wi W.JKK hoxo + Eiso R4/27
Σx exp Eis Wizzae + horo + Eiso hoTzs
Σ Emar exp En,, WiJ + ho + Eiso 1i21
Σ. exp Ei. Wi Wir + howo + Eiso 14:2
exp(hu) Exiroz1 exp E,, Wir + Eiso 1ep20
Σg exp En, We.gH,t h1z0 + Eizo hasrs exp(ha) Ex exp Eis Wiy + Eiso hig E. exp Ens WiyJzty + hozu + Esso hyTss
7

---

Published as a conference paper at ICLR 2025
Let now us define E(x) = exp Ein w1,y + Eiso Eishh for all æ. We have
exp(ho) En B(x)
Pr(s0 = 1]= exp(ho) Σ x= ((xr) + +exp(-ho) 2x:00=11 F(xr) Po
exp(ho) Ex F(xx)
(xp(ho) Σ, ((x) + exp(-hup Σ2 E(x)
exp Eg L'xx)
exp(2ha)
(2p()h)) E.. F(xx) + Σx F(x) exp(2ho) +
We shall now define another Ising model Q over 2o. .o..,........................... In as follows. The model Q has parameters {wi a. and {MA) so that wh, = way if (i, j) * (0, and wh.s- == wo, ò for some ò 1, and
h!g h; for all i. We have that for all E {-1, 1 it is the case that
((x) exp
Σ Eul
Σ hlaa
exp Σ wl, + Σ hios
= exp
(Wo,k + 8) rook +
Wiggtay +
Σ hers
(1,))(00.A)
exp
Wo, + Sangt +
Σ
WI + Σ lesars
(.,))+(0,A)
6xgga + Σ
WeyDz + Σ hip
= exp
= exp(6x00x)) exp
WiJTTHy Σ 1,1
+ Σ h1 = exp(8x00x) Polx) ZPo
whereby Zr, the partition function of Po- If TD = 1, then ((x) x exp(X) Po(x); else
Q(x) exp(-)) Po(z). Moreover, for any x such that 2g
((x) exp(0) Po(x)= Zro
ZQ
exp(6) Po(x) Zro
Σ Emzgrs (x)()) P)(x)) Zp, Σ -x
expl Po(x) Zp.
Po(x)
Σ Emiroe Po(x) expl (xxp(22)) 2 -11 Po(x)
Po(x)
Po(x)
Po(x))
1 Po(x) Ex:ror==1
Pa(x) Σ. Po(x)
where Za is the partition function of Q. Similarly, for any x such that TO = 1,
Q(x) = exp(-6) Pa(x) Zr,
Zo
expl 5) Po(x) Zro
Σ - (xp(6) Po (z) Zpo Σ - exp(-5) Po(x) Zp
(z(
Em Po(x)) Σ Emanp
8

---

Published as a conference paper at ICLR 2025
Po(x)
Po(z).
m= Po(x) + Ex 2 Pa(a)
That Po (x) 2 Q (x) and only zo = 11 We now have
drv(Po: Q) = Σ max - Q(x))
E
(Po(z) Q(z))
(a(2)22(())
Σ
(Po(x) - -(())= =
Σ
Po(z)
E
Q(z).
-EEET==1
Moreover,
Σ
Po(x)
Pr(mox = -1]
Po
Pr(so 1, 2k -1] + Pr(zo 1, 26 = 1] Po
Po
Pr(zo 1] Pr(zz = -1] + Pr(xo 11 Pr(æ = 1]
Po
Po
Pr(so 1] Pr
Pr(mE mE = -11 1] + Pr(ro -1] Pr(r = 1]
Po
P
Po
Prizo 1] + 1 - Pr 1] Pr(fr 1]
Po
1'
exp(2h1)
1- exp(22h))
exp(2ho) 1 Pr 1],
exp(2hn)
whereby we have used the fact that Prr
[ = +1] = Pr [rt = 11]. That is,
exp(2110)
1 1 exp( Priza 1].
dr Q) = exp(2ho) +1
Σ
Q(x) +
(2)
exp(2ho) + 1
=:
Note that
exp(-0) (z) Zpo
exp( (5) Zro
0 Σ Q
Σ
Zq
Zq
Intuitively, note that if (in the above) we set 5 - 00 and ho - -00, then drv (Prv(P.. Q) Pro[zs = 1], and an approximation of drv(Po, Q) implies an approximation of Prplæz 1].
Now we make this formal by finitely quantifying ho,
would suffice to show that
drv (Po. Q) Prin 11 S Prim* 1].
P
Then this could be combined with ğ m-mulipllcattive approximation of drv drv Q) to yield the desired e-multiplicative approximation of (x = 1]. By Equation (2)
(Po Q) Pr(m 11 P
exp (2ha) + + exp (-5) Zno
exp (2ha)
exp (2ha) Pr(m 1] exp (2ho) 1
72
2 2exp(2ho) + exp (-5)
Zo
Let W == maxi, Wiyl and H == max; lhs/. Then for any xr
exp Eis wijzi + E, har:)
Pr(ex = 1] Σ
2:11=1 E, exp Eis Wi.iVily + E; halss
2n-1 2n-lexp -W (n + 1)² (n + 1) H)
2n+1 exp
W (n + 1)² + (n +

---

Published as a conference paper at ICLR 2025
exp -W (n (n+ 1)² - (n 1)
4exp W (n+ 1)2 (n (n+1)11
Choosing ho and 8 such that max(-ho. 6) I(poly(n, H, W. 1/2, Zp/ Zz)) ([poly(n, H, W, 1/2)) (note that n Zo can bounded by some polynomial in n, H, W) we may ensure the desired
cxp
(n (n
- W (1+
2 2exp(2hh))
exp(-6)Zz) Zm
4 exp W (n + 1)² (n
Zq
An identical the above argument can be employed get a multiplicative approximation of Prp(æz = =1] (by letting hg - oo above).
Since drv(Po, Q) multiplicatively approximates Prplæg =1], this an approximation preserving reduction, as any multiplicative approximation of drv (Po. Q) is multiplicative approximation of Pry[æ4 =1].
4.3 PROOF OF THEOREM
To prove Theorem we shall require the following result Jerrum & Sinclair (1993).
Theorem 8 (Jerrum & Sinclair (1933). NP & RP, then there is no FPRAS that estimates the partition function of any Ising model.
We now turn the proof of Theorem 2
By Proposition 6 there exists some FPRAS that estimates any atomic marginal of any lsing model, then there exists some FPRAS that estimates the partition function of any Ising model. By Proposiiion 7| if there exists some FPRAS that estimates the TV distance between Ising models, then there exists is, if there exists some FPRAS that estimates the TV distance between Ising models, then there exists some FPRAS that estimates the partition function of any Ising model. By Theorem 8 NP Z RP, then there is no FPRAS that estimates the partition function of any Ising model. That is, NP g RP. then there no FPRAS that estimates the TV distance between Ising models. This concludes the proof.
Proof of Theorem 2
FPRAS that estimates any atomic marginal of any Ising model. That
5 DISCUSSION
We have shown how efficiently check whether mixtures of product distributions equivalent or not. One might wonder whether our ideas can be applied to check equivalence between mixtures of other, more expressive, kinds of distributions, such as Bayes nets.
Bayes nets constitute Pearl (1989) a probabilistic graphical model, with numerous applications in machine learning and interence, that naturally generalize product distributions in that they allow for dependencies among different variables. Bhattacharyya et al. (023) showed that it is NP-hard to not,
decide whether the total variation distance between two Bayes nets P and Q is equal so one cannot hope to extend our methods to testing equivalence between mixtures of Bayes net distributions (unless, of course, mixtures of some subclass of Bayes net distributions, such as Bayes net distributions whereby their underlying graph is a tree or has small treewidth?
NP.) Can our ideas be extended testing equivalence between
Our second result, namely the hardness of approximating the TV distance between Ising models, helps us further understand the intricacies of the Ising model and the consequences of complexity-theoree conjectures such as NP g RP. Can extend this complexity -theoreett hardness of approximation to other classes of probability distributions, such as factor graphs or general undirected probabilistic graphical models?
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
DesCartes: This research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. This work was supported in part by National Research Foundation Singapore under its NRF Fellowship Programme acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2024-05956 The work of AB was supported in part by National Research Foundation Singapore under its NRF Fellowship Programme (NRF-NRFFAL- 2019-0002) and an Amazon Faculty Research Award. The work of SG was supported in part by the SERB award CRG/2022/007985. Pavan's work is partly supported by NSF awards 21 305536, 2342245, 2413849. Vinod's work is partly supported by NSF awards 2130608, 2342244, 2413848.
COFF-NFFFAII-25 1111-200000004 and an Amazon Research Award. We
REFERENCES
Sanjeev Arora and Boaz Barak. Computational Complexity A Modern Approuch. Cambridge University Press, 2009, ISBN 47840-521-44426-44 URL http: /ttp///wwww//...///////////w./ cambridge org/
aataalouue/cttaloquee oa
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep Meel, and N. Vinodchandran. Efficient distance approximation for structured high-dimensional distributions via learning. In Proc. of NeurlPS, 2020.
Arna Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinodchandran. On approximating total variation distance. In Proceedings of IJCAI, 2023.
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinodchandran. Total variation distance meets probabilistic inference. In Forty-firsi International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. httt:ttts:///eeeeeeee
net. www.fooooooo0so00 ErBhh
Barry A. Cipra. An introduction to the Ising model. American Mathematical Monthly, 94:937-959, 1987. URL httptttst//p...seettst sewp:///tp....mtt......... cecccccchllccccoco wwt.hhoollaa..rro/rossrttsst 10115882144
Corinna Cortes, Mehryar Mohri, and Ashish Rastogi. Lp distance and equivalence of probabilistic automata, Int. Found. Comput. Sci., 18(4)7711-77, 2007.
Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006.
Peter Dixon, Sutanu Gayen, Aduri Pavan, and N. V. Vinodchandran. Perfect zero knowledge: New upperbounds and relativized separations. In Rafael Pass and Krzysztof Pietrzak (eds.), Proc. of TCC, volume 12550 of Lecture Notes in Computer Science, pp. 684-704 Springer, 2020.
Cynthia Dwork. Differential privacy. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (eds.), Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10- 14. 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pp. 1-12. Springer, 2006.
Weiming Feng, Heng Guo, Mark Jerrum, and Jiaheng Wang. A simple polynomial-time approxima- tion algorithm for the total variation distance between two product distributions. TheoretiSS, 2023.
Weiming Feng, Liqiang Liu, and Tianren Liu. On deterministically approximating total variation distance. In Proceedings of SODA, 2024.
Michael E. Fisher. On the Dimer Solution of Planar Ising Models. Journal of Mathematical Physics, 7710) 10 1966. ISSN 0022-2488. doi: 10. 12.1063/11104499 URI. https 7/doi . 1tt.:o////....//1111..
006311 111116117111..1...1111111111111
Yoav Freund and Yishay Mansour. Estimating a mixture of two product distributions. In Proceedings of COLT, 1999.
11

---

Published as a conference paper at ICLR 2025
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, pp. 467-484, 1999.
Spencer Gordon, Bijan H. Mazaheri, Yuval Rabani, and Leonard J. Schulman. Source identification for mixtures of product distributions. In Conference on Learning Theory, COLT, 2021.
Spencer L. Gordon and Leonard J. Schulman. Hadamard extensions and the identification of mixtures of product distributions. IEEE Trans. Inf. Theory, 68(6):4085 4089, 2022.
Spencer L. Gordon, Erik Jahn, Bijan Mazaheri, Yuval Rabani, and Leonard Schulman. Identification of mixtures of discrete product distributions in near-optimal sample and time complexity. CoRR, abs/2309.13993 2023.
Ernst Ising. Beitrag zur theorie des ferromagnetiismus Zeitschrif für Physik, 31:253-258, 1925.
URL https: / /api. semant htt.://cwc........o.oooorraaaaaa
Sorin Istrail. Statistical mechanics, three-dimensionalit and NP-completeness: universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract). In Proceedings of the Shirty-Seconl Annual ACM Symposium on Theory of Computing, STOC '00, 87-96, New York, NY, USA, 2000. Association for Computing Machinery. ISBN http://t....g...11111/////./11/1
13814, doi: 10.1145/335305.33553 URL
635316
Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput., 2285::107- 1993.
P. W. Kasteleyn. Dimer Statistics and Phase Transitions. Journal of Mathematical Physics, 4(2): 287-293, 02 1963. ISSN 0022-2488. doi: 1063/1. 1703953
URL /tt.:at:://....0///////
Stefan Kiefer. On computing the total variation distance of hidden Markov models. In Proc. of ICALP, pp. 130:1-130:13, 2018
W Lenz. Beitrag zum Verständnis der magnetischen Erscheinungen festen Körpern. Z Phys., 21: 613-615, 1920. URL httt:://css.cerm.cc//eeeeo
Rune Lyngsø and Christian S. Pedersen. The consensus string problem and the complexity of comparing hidden Markov models. J. Comput. Syst. Sci., 65(3):545-569 2002.
Lior Malka. How to achieve perfect simulation and complete problem for non-interactive perfect zero-knowledge. J. Cryptol., 28(3):533-550, 2015.
Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
Judea Pearl. Probabilistic reasoning in intelligent systems networks of plausible inference. Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989.
Yash Pote and Kuldeep S. Meel. Testing probabilistic circuits. In Proc. of NeurlPS, 2021.
Amit Sahai and Salil P. Vadhan. A complete problem for statistical zero knowledge. J. ACM, 50(2): 196- 196-249, 2003.
Shai Shalev-Shwart and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
Douglas Stinson. Cryptography theory and practice. Discrete mathematics and its applications series. CRC Press, 1995.
Salil P. Vadhan. Pseudorandomness. Found. Trends Theor Comput. Sci., 7(1-3):1-336, 2012.
Dominic Welsh. Complexity: Knots, Colourings and Counting. London Mathematical Society
Lecture Note Series. Cambridge University Press, 1993.
12

---

Published as a conference paper at ICLR 2025
A THE EXPRESSIBILITY OF MIXTURES OF PRODUCTS
We require the following observation.
Observation 9. Let D be distribution over Σ" for some alphabet E. Then for k == |Σ there exists a mixture of product distributions (w1...., Wk: Pi...., Pk) over En such that for all "" it is the case that
D(x) Σ w,P.(x).
Proof. Let .1,..., ......,,,, Ty be the elements of E" For all < k. let P. be a product distribution on n variables such that (.(y) = 1 if = F3 otherwise, P:(0) = We can construct such a product distribution P; as follows. First, note that (y( 1I Pig P,.((;)) whereby (z, is the probability that the j-th coordinate of P; takes the value 2 E Σ. Let 2i, Ji,n. whereby zijj Σ. Then for all define Pr.j (z) = if = Fi.j otherwise, Pi.j = Moreover, let wy := Da;))
and note that Σ Wi = 1. Then the desired equality follows by straightforward calculations.
B PROOF OF PROPOSITION 6
Let us first assume that there is some FPRAS M that runs in time tM and estimates any atomic marginal of any Ising model. We will prove there is some FPRAS that estimates the partition function of any Ising model.
Let P1 be an Ising model over variables .I,..., partition function Z1. We will show how to estimate Z1. To this end, let us define new Ising model P2 over variables .2,....;T In with parameters ( hi
In with parameters (ws.sks and (ha), with
and (1 (2) so that w = wis
and h ( W1,t + h2 for all 2 2 Let Ze be the partition function of Pp. Let also
E (x) == exp Σ
Σ hips
E2(x) exp
Σ G3
why
Bay +
Σ 1
(2)
for all v, and note that Z1 = Σn (1)) and Ze = Σn E2(x). We have
Σ Ex(z) = Σ
exp Σ
WiJJzZ + Σ hiW
==
==1==1
ijj
Σ exp
Σ
WigT + Σ 1 + Σ
hear + by
1,#1
i#1
Σ
exp
Σ
Wi
+
Σ
(wis + h1) xz + b
2:0
Σ
exp
Σ
Wig
Σ
(wi, + hs) x. exp(In
$1#1
exp(111
Σ
exp
(wi, + h1))))
x=m==1
exp(In)
exp
Σ
W. Iz +
(2)
Σ
h
(2)
x:1==1
= exxp(hi)
Σ exp
Σ
w $
K +
>
h 112)a1
2
13

---

Published as a conference paper at ICLR 2025
exp(lii Σ E2(x) exp(hi) Zz.
Moreover,
-r Σ (i(r)
21
Bi(x).
Prp [1
Combining the above, we have that
exp(h1) Prp [1 [1
Z1
Σ 2:1==1
Ei(x) Zo
Pro 01
This equality yields a natural recursive algorithm for computing Z1, whereby the computation of Z reduced to the computation of Z2 by making Prp, [x] = 1]. This continues until we reach in the recursion some Ising model P, over the variable Tn. At this point the computation of Z,, is trivial, as
of the algorithm . that estimates the marginal
Z, = exp (1(TT)
exp (ex(-1(1)) (h((mm
We will now bound the approximation and confidence errors of this algorithm. Note that
exp(hi) exp h2 (2) exp h (m-1))
exp
Zi Z/
Zm Prr x1 = 1] Prr, T22 1 ..... Prp.-1 In-1 =1
Prp F1 =1
whereby each atomic marginal the denominator approximated with (1 + Eo) ratio for = e/n by making use of M. This yields the desired approximation ratio of
(I (1+ n-1 < (1) < 1 n 1 =
We similarly argue for the confidence ratio dp 8/n that yields the desired confidence ratio of 8. That is, the outlined reduction approximation preserving. What left to bound the running time of this recursive procedure. Let (nn) be the running time in question. We have that
T(n) T(n 1) + La (n, /0. 1/50) O(1)
or T(n) = O(n (m, 1/e0, 1/6o)) = (ppoy((,, 1/50. 1/60)) This concludes the proof.
14


Reviews:
[{"review_id": "RsuwwcEAQb", "reviewer": "Reviewer_VzEw", "summary": "This paper addresses the problem of computing the total variation distance (TV-distance) between high-dimensional distributions from a computational standpoint. For distributions with compact descriptions, calculating TV-distance poses significant challenges, as the direct approach incurs exponential time complexity relative to input size. The authors present two main contributions:\n\n(1) They provide a polynomial-time algorithm for determining whether two mixtures of product distributions are identical. \n\n(2) They establish the computational hardness of approximating the TV-distance between two arbitrary Ising models.\n\nThe first result is based on a simple and clever algorithm, the second result comes from the standard hardness result of approximating partition functions of Ising models. \n\nDue to the limited time for reviewing, I went through all the proofs and understood the main ideas; however, I did not verify every detailed calculation.", "questions": "I think the logic in lines 181–184 is incorrect, though the result is ultimately correct. The logic appears to use the implication $ A \\implies B $ to conclude $ \\neg A \\implies \\neg B $, which is not valid. The result holds, however, because $ P = \\sum_{i=1}^k w_i P_i^{\\leq n} $ and $ Q = \\sum_{i=1}^k v_i Q_i^{\\leq n} $, so if $ P \\neq Q $, then $ \\sum_{i=1}^k w_i P_i^{\\leq j} \\neq \\sum_{i=1}^k v_i Q_i^{\\leq j} $ for at least $ j = n $.\n\nFor line 451, it should be $ \\delta x_0 x_1 \\to \\delta x_0 x_k $. Additionally, some of the calculations in lines 441–458 are straightforward, so a few lines could be removed to streamline the presentation.\n\nIn the proof of Proposition 7, when setting parameters, it would be helpful to specify how small the parameter $ \\eta_0 $ ( and $h_0,\\delta$) needs to be to ensure that the relative error of the marginal probability remains smaller than $ O(\\epsilon / n) $. Could you clarify why machine precision is considered here? Would $ \\mathrm{poly}(N / \\epsilon) $ bits suffice to represent $ \\eta_0 $, where $ N $ denotes the input size?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main contribution of this paper is the first result: deciding whether two mixtures of product distributions are the same. Suppose we have $k$ product distributions $P_1, P_2, \\ldots, P_k$, where each $P_i$ is an $n$-dimensional product distribution, i.e., $X \\sim P_i$ is a vector $(X_1, X_2, \\ldots, X_n)$. The paper takes the prefix of $X$, namely $X^{\\leq j} = (X_1, X_2, \\ldots, X_j)$ for $j \\leq n$. This distribution is denoted by $P^{\\leq j}_i$. Then, they consider the mixture of $P^{\\leq j}_1, P^{\\leq j}_2, \\ldots, P^{\\leq j}_k$, denoted by $P^{\\leq j}$. The algorithm decides whether $P^{\\leq j}$ and $Q^{\\leq j}$ are the same for all $j$. The algorithm is based on induction from $j = 1$ to $j = n$. The base case is trivial. The difficult part is that for $P^{\\leq j}$ and $Q^{\\leq j}$, the support of the distribution can be as large as $\\exp(\\Omega(j))$. To reduce the computational cost, the algorithm finds a \"sketch\" of the two distributions. One needs to check whether $P^{\\leq j}(x) = Q^{\\leq j}(x)$ for exponentially many $x \\in \\Sigma^{j}$. For each $x$, the algorithm views $P^{\\leq j}(x) = Q^{\\leq j}(x)$ as a linear equation. Instead of checking an exponential number of linear equations, the algorithm finds a basis of the linear system, and the size of the basis is $\\text{poly}(n)$. Then the algorithm only need to check the equations in the basis.\n\nOverall, the algorithm and the definition of $P^{\\leq j},Q^{\\leq j}$ are simple and clever, and I think deciding whether two mixtures of product distributions are the same is a basic problem in statistics.", "weaknesses": "The hardness result follows from standard results. Proposition 6 provides a self-reduction for the Ising model, which is used in the standard counting-to-sampling reduction. Therefore, the proof of Proposition 6 could be omitted. Proposition 8 essentially states that one can fix the value of a vertex $v$ by adjusting the function $h(v)$, allowing the TV distance to encode the marginal distribution.\n\nThe relationship between Theorem 1 and Theorem 2 is not very strong, as they pertain to different models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tr7pQkQwOK", "reviewer": "Reviewer_Zs6J", "summary": "The paper discusses computational aspects of the total variation (TV) distance between probability distributions and has two contributions:\n\nIt provides a deterministic polynomial-time algorithm for testing whether two mixtures of product distributions are equivalent, which means the algorithm can decide whether the TV distance between them is zero.\n\nIt demonstrates that, unless NP is contained in RP, there cannot exist an efficient algorithm to estimate the TV distance between arbitrary Ising models. This result points out the computational hardness of this problem.", "questions": "Can the equivalence checking algorithm be extended to other type of mixtures, say Bayesian networks with bounded treewidth?\n\nIs there any hope to soften the hardness assumption in estimating TV distance between Ising models by considering restricted classes of models?\n\nDo the authors have some recommendations for practical algorithms that could approximate the TV distance between Ising models despite the hardness result?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper addresses important computational questions about the total variation distance, which is fundamental in probability and statistics.\n\nThe algorithm for equivalence checking of mixtures of product distributions is new and provides a practical solution to a non-trivial problem.This hardness result bridges complexity theory and statistical measures and provides insight into why certain computational tasks are hard.\n\nThe proofs are well written, the results are accessible.", "weaknesses": "It would be nicer if the paper could elaborate more on the practical applications of the equivalence checking algorithm with regard to performance on real-world data.\n\nThe hardness result could also be pushed further by thinking about the possibility of approximate algorithms with different complexity assumptions.\n\nIt would be even more applicable and helpful with more examples or case studies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HkkjDh7wlr", "reviewer": "Reviewer_5F2F", "summary": "The paper has two main contributions: (1) An algorithm for checking equivalence for mixtures of product distributions (2) A hardness reduction for approximating the total variation distance between two Ising models.\n\nThe problem of checking equivalence of product distributions is takes the following as input: we are given $w_1,\\cdots, w_k, P_1,\\cdots,P_k$ and $v_1,\\cdots, v_k, Q_1,\\cdots,Q_k$ where:\n1) Each of $P_1,\\cdots,P_k$ and $Q_1,\\cdots,Q_k$ is a product distribution over $\\Sigma^n$.\n2) $w_1,\\cdots, w_k$ are the weights for $P_1,\\cdots,P_k$ and $v_1,\\cdots, v_k$ are the weights for $Q_1,\\cdots,Q_k$.\nSo, the first distribution $P$ is the mixture of $P_1,\\cdots,P_k$ each weighted by  $w_1,\\cdots, w_k$  and the second distribution $Q$ is the mixture of $Q_1,\\cdots,Q_k$ each weighted by  $v_1,\\cdots, v_k$. The task is to determine wether the two mixture distributions are the same.\n\nHere is an example (from page 2) an equal mixture of $Bern(1/3)$ and $Bern(2/3)$ equals to the distribution $Bern(1/2)$. This illustrates how a mixture of two product distributions can equal a different product distribution.\n\nThe paper gives a deterministic algorithm whose run-time is $O(nk^4 |\\Sigma|^4)$ which is polynomial in the input size which equals $kn|\\Sigma|$. One idea the algorithm uses is that if the two mixtures $w_1P_1+,\\cdots, +P_kw_k$ and $v_1Q_1+,\\cdots, +v_k Q_k$ are equal, then (after a normalization) the mixtures $w_1P_1+,\\cdots, +P_jw_j$ and $v_1Q_1+,\\cdots, +v_j Q_j$ are also equal for every $j$. The algorithm utilizes the idea by iteratively establishing equivalence for $j=1,2..., k$ at every step $j$ establishing equivalence for $j+1$ assuming equivalence for $j$ (or to find some $x$ for which the probabilities of two distributions differ). As the paper shows, such steps can be achieved by keeping track of bases for solutions of certain types of equations.\n\nIsing models are a fundamental family of probability distributions over $\\{\\pm 1\\}^n$. Probability of each $x$ in $\\{\\pm 1\\}^n$ is proportional to $\\exp(P(x))$ where $P$ is a degree-2 multilinear polynomial. Ising models are a very well-studied family of distributions modeling systems for which random features have only pairwise interactions (this is because each term in $P$ has at most two variables). \n\nA Fully Polynomial-time Randomized Approximation scheme FPRAS is a randomized algorithm that gives a multiplicative $(1+\\epsilon)$-approximation to a desired quantity. Here, this means that one is given a pair of degree-2 polynomials $P_1$ and $P_2$ describing a pair of Ising models, and the goal of the algorithm is to output a multiplicative $(1+\\epsilon)$-approximation to the TV distance between the pair of Ising models. The paper shows that no poly-time algorithm can achieve this task (under a basic complexity-theoretic assumption).\n\nThe hardness proof proceeds by developing an approximation-preserving reduction to the problem of approximating the partition function of an Ising model, which is known from previous work to be hard to approximate. As an intermediate step, the reduction goes through the problem of approximating the marginal of an Ising-model distribution on one of the coordinates $x_i$ (this is referred to as the problem of approximating the atomic marginal).", "questions": "- Was a poly-time randomized algorithm for checking equivalence of mixtures of product distributions known previous to this work?\n- To the best of your knowledge, what was known from previous work about approximating TV distance between Ising models?\n- Do your hardness result tell us anything about hardness of computing an additive approximation for the TV distance between Ising models?\n- Does the problem of estimating the TV distance between Ising models remain to be hard if one is given the values of the partition function $Z_1$ and $Z_2$ for each of the Ising models?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Mixtures of products are a fundamental family of probability distributions and checking their equivalence is one of the most basic questions about them.  \n- The algorithm uses an interesting novel idea of keeping track of bases for the solution spaces of certain equations. This idea might find applications for testing equivalence of other classes of distributions.\n- The problem of estimating the total variation distance between two Ising model distributions is quite natural, as Ising models are a very well-studied class of probabilistic models.\n- The hardness result only relies on the assumption that NP is not in RP, which is a very mild complexity assumption.", "weaknesses": "- The algorithm for mixtures of product distributions can only check whether P=Q exactly. The paper would be stronger if it gave an algorithm for approximating the distance between P and Q.\n- The paper rules out FPRAS for TV distance between a pair of Ising models, but it seems that there could still be a constant-factor approximation algorithm, and the paper would be stronger if this question was also addressed (i.e. it was shown that this is also hard, or an algorithm was given).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bYXPOhWlJw", "reviewer": "Reviewer_1jgf", "summary": "The paper studies some properties about the complexity of computing the Total Variation Distance between distributions. The authors consider  the case of the mixure of product distributions and the case of Ising models. In the first case they show a polytime algo that has access to the marginals and checks the equivalnece of two mixtures. For the second case they show hardness of approximating TVD by an FPRAS  under the hypothesis NP not included in RP.\nThe two results are sound and well written. \nHowever, the contribution is limited. \nI think neither of the two results are very significant alone and together the overall contribution is not very much more.", "questions": "The paper mentions some open questions but is there any chance that the techniques used, e.g., in the first theorem can be extended to other types of more general distributions? (I personally doubt it)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper give two new results about computing TVD. \nThe polynomial time algorithm for TVD of mixtures of product distribution has its main strength in the simplicity and clarity of the approach.\nThe second result extends the studies on the complexity of dealing with Ising models.", "weaknesses": "The paper appears to be a gluing of two minor results with little connection between them. \nThe second result  builds upoon the Jerrum and Sincler previous analogous study. The first result bears more novelty, although it would not be, in my opinion, sufficient for a paper at ICLR.\nI think the main issue is with the specificity (very particular cases) of the two problems solved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JIzShc1XMK", "reviewer": "Reviewer_riHb", "summary": "This paper studies two fundamental questions about high-dimensional probability distributions.\n\n1. Is there a polynomial-time algorithm which can decide whether two *mixtures of product distributions on the hypercube* are equal to each other?\n2. Is there a polynomial-time algorithm which can accurately approximate the total variation distance between two Ising model distributions?\n\nThe paper answers (1) affirmatively, giving a very nice linear algebraic algorithm which can test equivalence between mixtures of product distributions on the cube, given access to the parameters of the distributions.\nThe paper answers (2) negatively, showing that unless NP is contained in RP (that is, unless NP-complete problems have randomized polynomial time algorithms), the total variation distance between Ising models is inapproximable.\n\nStrengths:\nThe paper studies truly fundamental problems which will be of broad appeal to the ICLR audience.\nThe results are convincing, and the equivalence-checking algorithm is very nice.\n\nWeaknesses:\nThese problems are so fundamental that it is a little hard to believe they are not already well studied.\nIt would be nice if the related work section were expanded.\nIt would be nice if the algorithm also meant you can test equivalence given samples.\n\nOverall, I recommend accepting the paper to ICLR, on the basis that the results are about a very fundamental set of problems, and the equivalence testing algorithm is very clean.\n\n\nQuestions:\n- Does result (1) mean you can also do equivalence testing from samples?\n- Is the linear algebraic method you describe similar to any existing equivalence tester in the literature?", "questions": "see above", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "see above", "weaknesses": "see above", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)