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

476次阅读
没有评论

静5青年讲座 | Approximate Counting for Spin Systems...静5青年讲座 | Approximate Counting for Spin Systems...静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

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

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青年讲座 | Approximate Counting for Spin Systems...

往 期 讲 座

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

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

—   版权声明  —

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

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

“阅读原文”查看海报

 

Read More 

正文完
可以使用微信扫码关注公众号(ID:xzluomor)
post-qrcode
 
评论(没有评论)
Generated by Feedzy