A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
- Dr. Weiming Feng, University of Edinburgh
- Time: 2023-02-21 16:00
- Host: Dr. Tongyang Li
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
The total variation (TV) distance is a fundamental metric to measure the difference between two distributions. Recent work by Bhattacharyya et. al. proved that the exact computation of the total variation distance, even between two product distributions over the Boolean domain, is #P-hard. In this talk, I will give a simple polynomial-time approximation algorithm for the total variation distance between two product distributions.
This talk is based on joint work with Heng Guo, Mark Jerrum and Jiaheng Wang. The paper (5 pages) is accepted by SOSA 2023.
Biography
Weiming Feng is a research associate (postdoc) at the School of Informatics, University of Edinburgh. He obtained his PhD degree from Nanjing University in 2021, where his supervisor is Prof. Yitong Yin. His research focuses on Theoretical Computer Science, with an emphasis on sampling and counting algorithms. He has published a series of papers in JACM, SICOMP, STOC, FOCS and SODA.