• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Computational Explorations of Total Variation Distance.
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, A. Myrisiotis, Dimitriosand Pavan and N. V. Vinodchandran.
In Proceedings of the International Conference on Learning Representations (ICLR), .
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 𝖭𝖯$\subseteq$𝖱𝖯, it is impossible to efficiently estimate the TV distance between arbitrary Ising models, even in a bounded-error randomized setting.
@inproceedings{BGPMMPV25,
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,
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 𝖭𝖯$\subseteq$𝖱𝖯, it is impossible to efficiently estimate the TV distance between arbitrary Ising models, even in a bounded-error randomized setting.
}
bib2html_rescat={Distribution Testing},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={https://arxiv.org/abs/2412.10370},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Mon Dec 01, 2025 18:50:36