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

Weiming Feng; Heng Guo; Mark Jerrum; Jiaheng Wang

doi:10.46298/theoretics.23.7

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

Weiming Feng, Heng Guo, Mark Jerrum, Jiaheng Wang^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

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

Original language	English
Article number	8
Pages (from-to)	1-7
Journal	TheoretiCS
Volume	2
DOIs	https://doi.org/10.46298/theoretics.23.7
Publication status	Published - 12 Jun 2023

Keywords / Materials (for Non-textual outputs)

total variation distance
product distribution
approximation algorithm

Access to Document

10.46298/theoretics.23.7Licence: Creative Commons: Attribution (CC-BY)

A simple polynomial_FENG_DOA15052023_VOR_CC BYFinal published version, 292 KBLicence: Creative Commons: Attribution (CC-BY)

https://doi.org/10.46298/theoretics.23.7Licence: Creative Commons: Attribution (CC-BY)

New Approaches to Counting and Sampling
Guo, H.
EU government bodies
1/01/21 → 31/12/25
Project: Research

Cite this

@article{ec699ef7b58045b5992a12e6ca5322b4,

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

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

keywords = "total variation distance, product distribution, approximation algorithm",

author = "Weiming Feng and Heng Guo and Mark Jerrum and Jiaheng Wang",

note = "MJ was supported by grant EP/S016694/1 {\textquoteleft}Sampling in hereditary classes{\textquoteright} from the Engineering and Physical Sciences Research Council (EPSRC) of the UK. FWM, GH, and WJH have received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No. 947778). WJH has also received financial support from an Informatics Global PhD Scholarship at The University of Edinburgh. ",

year = "2023",

month = jun,

day = "12",

doi = "10.46298/theoretics.23.7",

language = "English",

volume = "2",

pages = "1--7",

journal = "TheoretiCS",

issn = "2751-4838",

}

TY - JOUR

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

AU - Feng, Weiming

AU - Guo, Heng

AU - Jerrum, Mark

AU - Wang, Jiaheng

N1 - MJ was supported by grant EP/S016694/1 ‘Sampling in hereditary classes’ from the Engineering and Physical Sciences Research Council (EPSRC) of the UK. FWM, GH, and WJH have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 947778). WJH has also received financial support from an Informatics Global PhD Scholarship at The University of Edinburgh.

PY - 2023/6/12

Y1 - 2023/6/12

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

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

KW - total variation distance

KW - product distribution

KW - approximation algorithm

U2 - 10.46298/theoretics.23.7

DO - 10.46298/theoretics.23.7

M3 - Article

SN - 2751-4838

VL - 2

SP - 1

EP - 7

JO - TheoretiCS

JF - TheoretiCS

M1 - 8

ER -

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

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

New Approaches to Counting and Sampling

Cite this