Computational Explorations of Total Variation Distance

Autor:	Bhattacharyya, Arnab, Gayen, Sutanu, Meel, Kuldeep S., Myrisiotis, Dimitrios, Pavan, A., Vinodchandran, N. V.
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	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. Comment: 17 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2412.10370 Zobrazit plný text záznamu View this record from Arxiv