2026-09-10T09:44:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27768 2026-09-09T12:19:37Z ddc:004 open_access

On Computing Total Variation Distance Between Mixtures of Product Distributions Feng, Weiming Fu, Yucheng Yang, Minji Zhang, Anqi Randomized algorithm Total variation distance 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 ℙ and ℚ with k₁ and k₂ product distributions over [q]ⁿ, respectively, we give a randomized algorithm that approximates d_TV(ℙ,ℚ) within a multiplicative error of (1±ε) in time poly((nq)^{k₁+k₂}, 1/ε). We also study the special case of mixtures of Boolean subcubes over {0,1}ⁿ. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time poly(n, 2^O(k₁+k₂)), and show that exact computation is #𝖯-hard when k₁+k₂ = Θ(n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Weiming Feng and Yucheng Fu and Minji Yang and Anqi Zhang 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.51 urn:nbn:de:0030-drops-277689 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.51 eng https://creativecommons.org/licenses/by/4.0/legalcode