Postponed.
ENS, S16.
On Approximating Total Variation Distance
Abstract: Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. we introduce and study the problem of computing the TV distance between two product distributions over the domain {0,1}^n. In particular, we establish the following results.
- The problem of exactly computing the TV distance between 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.
- There is a fully polynomial-time deterministic approximation scheme (FPTAS) for computing the TV distance between 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.
We also discuss some very recent results of ours on approximating TV distance between two Bayes nets with bounded treewidth.
Joint work with Sutanu Gayen (IIT Kanpur), Kuldeep Meel (NUS), Dimitrios Myrisiotis (NUS), A. Pavan (Iowa State), and N.V. Vinodchandran (U. Nebraska Lincoln).
Short bio: Arnab Bhattacharyya is an assistant professor at the School of Computing, National University of Singapore. He obtained his bachelor’s, master’s and doctoral degrees in computer science from the Massachusetts Institute of Technology. Subsequently, he was a postdoctoral associate at Princeton University and Rutgers University, and an assistant professor and a Ramanujan Fellow at the Indian Institute of Science, Bangalore. He is the recipient of an Amazon Faculty Research Award, a National Research Foundation (Singapore) Fellowship in AI, and a Google Faculty Research Award (for South/Southeast Asia).
His research area is theoretical computer science and foundations of data science, in a broad sense. Specifically, he is interested in algorithms for problems involving high-dimensional data, causal inference, sublinear time algorithms, complexity theory, and algorithmic models for physical systems.
