关键词：静5青年讲座
编者按
2023年2月21日，爱丁堡大学的凤维明博士受邀访问北京大学前沿计算研究中心，并在静园五院做了题为“A simple polynomial-time approximation algorithm for the total variation distance between two product distributions”的学术报告。报告由中心助理教授李彤阳老师主持。
凤维明博士报告现场
在报告的开始，凤博士首先介绍了基础概念，例如如何衡量两个分布间的距离，以及直观地给出了问题的背景。
出人意料的是，计算高维分布间的距离这一看似简单的问题事实上与一系列复杂的问题拥有相同的复杂度。
凤博士随后给出了简单的例子来说明这一问题复杂的部分来源于随机变量在不同维度下的关联性，以及引出运用耦合已获得近似算法巧妙的估算目标值。
之后，凤博士利用贪心算法以及精妙的误差估计，获得了对于分布间的距离的一个无偏估计，并由此得到了对目标问题所需的近似算法。
值得注意的是，这篇论文仅仅5页，可见在耦合这一强大的随机分析工具的使用对于证明简化的帮助。最终，凤博士针对确定性近似算法、一般高维分布的类似问题提出展望。
参考文献
[1] Feng W, Guo H, Jerrum M, et al. A simple polynomial-time approximation algorithm for the total variation distance between two product distributions[C]. Symposium on Simplicity in Algorithms (SOSA). Society for Industrial and Applied Mathematics, 2023: 343-347.
图文 | 魏智德
往期讲座
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。