# Computational Explorations of Total Variation Distance

arXiv: https://arxiv.org/abs/2412.10370 · HTML: https://mlsanity.com/paper/2412.10370/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2024.

## Built on by (most cited first, 3 of 3)

- [Approximating the total variation distance between spin systems](https://mlsanity.com/paper/2502.05437/) (2025)
- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

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 mathsfNP subseteq mathsfRP, it is impossible to efficiently estimate the TV distance between arbitrary Ising models, even in a bounded-error randomized setting.