Total Variation Distance for Product Distributions is #P-Complete

2024/05/14 by Bhattacharyya, Arnab, Gayen, Sutanu, Meel, Kuldeep S. +3
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2405.08255

Abstract

We show that computing the total variation distance between two product distributions is #P-complete. This is in stark contrast with other distance measures such as Kullback-Leibler, Chi-square, and Hellinger, which tensorize over the marginals leading to efficient algorithms.

Related

• On Deterministically Approximating Total Variation Distance
• Computational Explorations of Total Variation Distance
• On the tensorization of the variational distance
• On distance in total variation between image measures
• Lower Bounds for the Total Variation Distance Given Means and Variances of Distributions