Skip to main content

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

Jiaheng Wang ( University of Edinburgh )

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: