ICLR 2025spotlight2 citations
Computational Explorations of Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran
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.
total variation distanceTV distancemixtures of productsequivalence checkingIsing modelscomputational complexityFPRAS
BibTeX
@inproceedings{
bhattacharyya2025computational,
title={Computational Explorations of Total Variation Distance},
author={Arnab Bhattacharyya and Sutanu Gayen and Kuldeep S. Meel and Dimitrios Myrisiotis and A. Pavan and N. V. Vinodchandran},
booktitle={The Thirteenth International Conference on Learning Representations},
year={2025},
url={https://openreview.net/forum?id=xak8c9l1nu}
}