On Deterministically Computing Total Variation Distance via Zonotope Compression

Yucheng Fu

In the authors' words

We study deterministic relative approximation of the total variation distance between high-dimensional distributions given by succinct descriptions. We develop an abstract deterministic approximation framework based on representing the total variation distance as a support function of a low-dimensional zonotope. As applications, we obtain FPTASs for several models. Given two mixtures of product distributions over $[q]^{n}$ with a total of $K$ component distributions, our algorithm approximates their TV-distance within a factor of $1 + ε$ in time $O_{K} (n q (n / ε)^{2 K})$ . We also give an FPTAS for mixtures of $n$ -step Markov chains over $[q]^{n}$ with a total of $K$ component distributions, with running time $O_{K} (n q^{2} (n / ε)^{2 K})$ . Finally, for two latent-tree Ising models with the same underlying tree topology, we give an FPTAS for the TV-distance between their leaf marginals in time $O (∣ V ∣^{13} ε^{- 12})$ .

Main resultThe abstract does not state a limitation.

On Deterministically Computing Total Variation Distance via Zonotope Compression

In the authors' words

More on Algorithms & complexity that day

Smoothed Analysis of Inconsistent A*

Hardness of Online Directed Steiner Network

Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

Parameter-Free Triangle Counting