Abstract

The total variation (TV distance is a fundamental metric between distributions.  Computing the exact TV distance is #P-hard.  A recent work (Feng, Guo, Jerrum and Wang) gives an poly-time randomized approximation algorithm for TV distance.  In this talk, we present a *deterministic* approximation algorithm.  

Our work is not de-randomizing the work of FGJW.  Instead, we borrow technique from the statistical decision theory.  The talk will start with a brief overview of decision theory.

Time

2023-06-17  14:00 - 14:30   

Speaker

Tianren Liu, Peking University

Room

Guangdong Hotel