Total Variation Distance for Product Distributions is #P-Complete

2024/05/14 by Arnab Bhattacharyya, Bhattacharyya, Arnab, Sutanu Gayen +9 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2405.08255

openalex publication_date 2024/05/14 · openalex created_date 2024/05/16 · openalex updated_date 2026/07/28

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.

Cited by

• Approximating the Trace Distance Between Product Quantum States

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