@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@inproceedings{BGMMAV23,
  title={On Approximating Total Variation Distance},
  author={
    Bhattacharyya, Arnab and
    Gayen, Sutanu and
    Meel, Kuldeep S and
    Myrisiotis, Dimitrios and
    A., Pavan and
    Vinodchandran, N. V.
  },
  abstract={
    Total variation distance (TV distance) is a fundamental notion of distance
    between probability distributions. In this work, we introduce and study the
    problem of computing the TV distance of two product distributions over the
    domain {0,1}^n. In particular, we establish the following results.
    1. The problem of exactly computing the TV distance of two product
    distributions is #P-complete. This is in stark contrast with other distance
    measures such as KL, Chi-square, and Hellinger which tensorize over the
    marginals leading to efficient algorithms.
    2. There is a fully polynomial-time deterministic approximation scheme
    (FPTAS) for computing the TV distance of two product distributions P and Q
    where Q is the uniform distribution. This result is extended to the case
    where Q has a constant number of distinct marginals. In contrast, we show
    that when P and Q are Bayes net distributions the relative approximation of
    their TV distance is NP-hard.
  },
  publication_type={conference},
  booktitle=IJCAI,
  year={2023},
  month=jul,
  bib2html_rescat={Distribution Testing},
  bib2html_pubtype={Refereed Conference},
  bib2html_dl_pdf={../Papers/ijcai23-bggmpv.pdf},
}