• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Computational Explorations of Total Variation Distance.
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan and N. V. Vinodchandran.
In Proceedings of the International Conference on Learning Representations (ICLR), 2025.
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.
@inproceedings{BGMMPV25a,
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=ICLR,
year={2025},
bib2html_rescat={Distribution Testing},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={https://arxiv.org/pdf/2412.10370},
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.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21