Computational Explorations of Total Variation Distance
The University of Warwick · Indian Institute of Technology, Kanpur · Department of Computer Science · CNRS@CREATE LTD. · Iowa State University · University of Nebraska, Lincoln
PDF 由论文原始站点提供，PaperCompass 不保存论文文件。
摘要
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.