静5青年讲座 | Approximate Counting for Spin Systems…

Approximate Counting for Spin Systems in Sub-Quadratic Time

报告人

Dr. Jiaheng Wang

University of Edinburgh

时  间

2023年9月19日 星期二 4:00pm

地  点

静园五院204

Host

孔雨晴 助理教授

 Abstract

We present two approximate counting algorithms with  running time for some constant  and accuracy  :

(1) for the hard-core model when strong spatial mixing (SSM) is sufficiently fast;
(2) for spin systems with SSM on planar graphs with quadratic growth, such as  .

The latter algorithm also extends to (not necessarily planar) graphs with polynomial growth, such as  , albeit with a running time of  . Our technique utilizes Weitz’s self-avoiding walk tree (STOC, 2006) and the recent marginal sampler of Anand and Jerrum (SIAM J. Comput., 2022).

Joint work with Konrad Anand (Queen Mary), Weiming Feng (UC Berkeley), Graham Freifeld (Edinburgh) and Heng Guo (Edinburgh). Available at arXiv:2306.14867.

Biography

Jiaheng Wang is currently a Postdoctoral Research Associate (PDRA) at the School of Informatics, University of Edinburgh. He obtained a PhD degree at the same university under the supervision of Heng Guo. Prior to that, he got a BSc degree at Peking University and was a member of the first Turing Class. He has a general interest in algorithms and complexity, with a focus on approximate counting problems.

往 期 讲 座

• 静5前沿讲座回顾 | 贝小辉教授谈广告拍卖中的实践与理论问题

• 静5前沿讲座回顾｜陆品燕教授介绍一价拍卖效率的确定

• 静5青年讲座回顾 | 徐海峰博士谈机器学习中的经济学

• 静5杰出讲座回顾｜叶荫宇教授谈随机Fisher市场中的在线均衡标价问题

—   版权声明  —

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

点“阅读原文”查看海报