Computational Explorations of Total Variation Distance
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.
Cite
Text
Bhattacharyya et al. "Computational Explorations of Total Variation Distance." International Conference on Learning Representations, 2025.Markdown
[Bhattacharyya et al. "Computational Explorations of Total Variation Distance." International Conference on Learning Representations, 2025.](https://mlanthology.org/iclr/2025/bhattacharyya2025iclr-computational/)BibTeX
@inproceedings{bhattacharyya2025iclr-computational,
title = {{Computational Explorations of Total Variation Distance}},
author = {Bhattacharyya, Arnab and Gayen, Sutanu and Meel, Kuldeep S. and Myrisiotis, Dimitrios and Pavan, A. and Vinodchandran, N. V.},
booktitle = {International Conference on Learning Representations},
year = {2025},
url = {https://mlanthology.org/iclr/2025/bhattacharyya2025iclr-computational/}
}