A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
Jiaheng Wang ( University of Edinburgh )
- 14:00 15th June 2023 ( week 8, Trinity Term 2023 )Lecture Theatre B
We give a simple polynomial-time approximation algorithm for the total variation distance between two product distributions.
To be more concrete, we show how one can achieve this in 5 pages (including the title page and references) by manipulating various tricks from probability theory, especially those for couplings. The exact computation, on the other hand, is known to be #P-complete and does not admit any polynomial-time algorithm unless FP=#P.
Joint work with Weiming Feng (Edinburgh), Heng Guo (Edinburgh) and Mark Jerrum (Queen Mary) that appeared in SOSA'23 (conference) and is to appear in TheoretiCS (journal).
Share this:
