Total Variation Distance for Product Distributions is $\#\mathsfP$-Complete
<|reference_start|>Total Variation Distance for Product Distributions is $\#\mathsfP$-Complete: We show that computing the total variation distance between two product distributions is $\#\mathsf{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.<|reference_end|>
@article{bhattacharyya2024total,
    title={Total Variation Distance for Product Distributions is
  $\#\mathsf{P}$-Complete},
    author={Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios
  Myrisiotis, A. Pavan, N. V. Vinodchandran},
    journal={arXiv preprint arXiv:2405.08255},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.08255},
    primaryClass={cs.CC}
}