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.




往 期 讲 座



—   版权声明  —

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

点“阅读原文”查看海报

内容中包含的图片若涉及版权问题，请及时与我们联系删除