A simple polynomial-time approximation algorithm for the total variation distance between two product distributions

Weiming Feng, Heng Guo, Mark Jerrum, Jiaheng Wang

Type: Book-Chapter

Publication Date: 2023-01-01

Citations: 0

DOI: https://doi.org/10.1137/1.9781611977585.ch30

Abstract

We give a simple polynomial-time approximation algorithm for the total variation distance between two product distributions.

Locations

arXiv (Cornell University) - View - PDF
Edinburgh Research Explorer (University of Edinburgh) - View - PDF
Edinburgh Research Explorer (University of Edinburgh) - View - PDF
Queen Mary Research Online (Queen Mary University of London) - View - PDF
Society for Industrial and Applied Mathematics eBooks - View

Similar Works

Action	Title	Year	Authors
+	A simple polynomial-time approximation algorithm for the total variation distance between two product distributions	2022	Weiming Feng Heng Guo Mark Jerrum Jiaheng Wang
+ PDF Chat	Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete	2024	Arnab Bhattacharyya Sutanu Gayen Kuldeep S. Meel Dimitrios Myrisiotis A. Pavan N. V. Vinodchandran
+	On Deterministically Approximating Total Variation Distance	2023	Weiming Feng Liqiang Liu Tianren Liu
+	On Approximating Total Variation Distance	2022	Arnab Bhattacharyya Sutanu Gayen Kuldeep S. Meel Dimitrios Myrisiotis A. Pavan N. V. Vinodchandran
+	On Approximating Total Variation Distance	2023	Arnab Bhattacharyya Sutanu Gayen Kuldeep S. Meel Dimitrios Myrisiotis A. Pavan N. V. Vinodchandran
+	A review on the products of distributions	2007	C. K. Li
+ PDF Chat	On Deterministically Approximating Total Variation Distance	2024	Weiming Feng Liqiang Liu Tianren Liu
+	Total Variation Distance for Poisson	2005	Larry Goldstein Gesine Reinert
+	A contribution to the equivalence results for the product of distributions	1994	Jiří Jelínek
+	Bounds for the total variation distance between second degree polynomials in normal random variables	2021	Egor D. Kosov
+	Bounds for the total variation distance between second degree polynomials in normal random variables	2021	Egor D. Kosov
+	Measures of distance between probability distributions	1989	J. K. Chung Pl. Kannappan C. T. Ng Prasanna K. Sahoo
+	A survey on distribution-free statistics based on distances between distribution functions	1968	W. Sahler
+	Lower Bounds for the Total Variation Distance Given Means and Variances of Distributions	2022	Tomohiro Nishiyama
+ PDF Chat	Variation-difference approximation	1980	S. G. Mikhlin
+	Distance Distributions	1977	Robin Sibson
+	A brief survey on probability distribution approximation	2019	Massimo Melucci
+	Upper and lower bounds for distance to measure approximation	2012	Quentin Mérigot
+ PDF Chat	Survey of Distances between the Most Popular Distributions	2023	Mark Kelbert
+	The total variation distance between high-dimensional Gaussians with the same mean	2018	Luc Devroye Abbas Mehrabian Tommy Reddad

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (3)

Action	Title	Year	Authors
+	Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs	2010	Parikshit Gopalan Adam R. Klivans Raghu Meka
+ PDF Chat	A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions	2012	Daniel Štefankovič Santosh Vempala Eric Vigoda
+	On Approximating Total Variation Distance	2023	Arnab Bhattacharyya Sutanu Gayen Kuldeep S. Meel Dimitrios Myrisiotis A. Pavan N. V. Vinodchandran