# On Approximating Total Variation Distance

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2022.

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

- [FARE: Provably Fair Representation Learning with Practical Certificates](https://mlsanity.com/paper/2210.07213/) (2022)
- [Provably Efficient UCB-type Algorithms For Learning Predictive State Representations](https://mlsanity.com/paper/2307.00405/) (2023)
- [Total Variation Distance Meets Probabilistic Inference](https://mlsanity.com/paper/2309.09134/) (2023)
- [A Thorough Assessment of the Non-IID Data Impact in Federated Learning](https://mlsanity.com/paper/2503.17070/) (2025)
- [Sharp bounds on aggregate expert error](https://mlsanity.com/paper/2407.16642/) (2024)
- [Bias Detection via Maximum Subgroup Discrepancy](https://mlsanity.com/paper/2502.02221/) (2025)
- [Approximating the total variation distance between spin systems](https://mlsanity.com/paper/2502.05437/) (2025)
- [Approximating the Total Variation Distance between Gaussians](https://mlsanity.com/paper/2503.11099/) (2025)
- [When Tabular Foundation Models Meet Strategic Tabular Data: A Prior Alignment Approach](https://mlsanity.com/paper/2605.19662/) (2026)
- [Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing](https://mlsanity.com/paper/2503.07775/) (2025)
- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)
- [New Algorithmic Directions in Optimal Transport and Applications for Product Spaces](https://mlsanity.com/paper/2509.21502/) (2025)
- [Comparing Labeled Markov Chains: A Cantor-Kantorovich Approach](https://mlsanity.com/paper/2511.18103/) (2025)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

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,1n. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is #mathsfP-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 mathsfNP-hard.