静5青年讲座 | A simple polynomial-time approximation algorithm...

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

报告人

Dr. Weiming Feng, University of Edinburgh

时  间

2023年2月21日 星期二 16:00

地  点

静园五院204

Host

李彤阳 助理教授

 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.

往 期 讲 座

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”查看海报