Kavli Affiliate: Anqi Zhang
| Summary:
We study the problem of approximating the total variation distance between two mixtures of product distributions over an $n$-dimensional discrete domain. Given two mixtures $mathbbP$ and $mathbbQ$ with $k_1$ and $k_2$ product distributions over $[q]^n$, respectively, we give a randomized algorithm that approximates $d_mathrmTVleft(mathbbP,mathbbQright)$ within a multiplicative error of $(1pm varepsilon)$ in time $mathrmpoly((nq)^k_1+k_2,1/varepsilon)$. We also study the special case of mixtures of Boolean subcubes over $,1^n$. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time $mathrmpoly(n,2^O(k_1+k_2))$, and show that exact computation is $#mathsfP$-hard when $k_1+k_2=Θ(n)$.
| Search Query:arXiv Query: search_query=au:”Zhang Anqi”&id_list=&start=0&max_results=10
Read More