{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T05:38:27Z","timestamp":1773639507205,"version":"3.50.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>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.\n\n\n\n1. 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.\n\n\n\n2. 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.<\/jats:p>","DOI":"10.24963\/ijcai.2023\/387","type":"proceedings-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:30Z","timestamp":1691742690000},"page":"3479-3487","source":"Crossref","is-referenced-by-count":10,"title":["On Approximating Total Variation Distance"],"prefix":"10.24963","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[{"name":"National University of Singapore"}]},{"given":"Sutanu","family":"Gayen","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kanpur"}]},{"given":"Kuldeep S.","family":"Meel","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Dimitrios","family":"Myrisiotis","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[{"name":"Iowa State University"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"University of Nebraska, Lincoln"}]}],"member":"10584","event":{"name":"Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}","theme":"Artificial Intelligence","location":"Macau, SAR China","acronym":"IJCAI-2023","number":"32","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2023,8,19]]},"end":{"date-parts":[[2023,8,25]]}},"container-title":["Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:47:31Z","timestamp":1691743651000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2023\/387"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2023\/387","relation":{},"subject":[],"published":{"date-parts":[[2023,8]]}}}