{"id":"arxiv/2609.18707","url":"https://arxiv.org/abs/2609.18707","tags":["cs.DS","math.PR"],"score":0,"title":"Total Variation Distance Estimation through Domain Reduction","domain":"cs.DS","source":"arxiv","authors":["Arnab Bhattacharyya","Graham Cormode","Yucheng Fu","Kuldeep S. Meel"],"reviews":0,"subject":"cs.DS","summary":"Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable. We give an FPRAS for TV distance between mixtures of product distributions and, more generally, for a natural class of structured probabilistic circuits. Our main technique is a novel application of domain reduction: Given a family of feature vectors indexed by assignments, we use Lewis-weight sampling to replace the assignment domain by a polynomial-size weighted subset that simultaneously approximates the sum of absolute values of every linear projection. For…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}