静5青年讲座回顾 | 王家恒博士谈Spin System上的近似计数

王家恒博士报告现场

王家恒博士的报告从一个大家都熟悉的独立集系统下的技术问题开始讲起。在理论计算机科学中，一个经典问题是图中的独立集近似计数问题。在这一问题的一个常见的扩展设定是对输入图  （点数为  ，保证最大度数不超过  ）近似计算一个 partition function 的值  ，即对于图中每个独立集  ，以  计入对输出的贡献，该问题称为  。理论计算机科学家希望能找到此问题的多项式随机估计算法（Fully polynomial-time randomized approximation scheme，FPRAS）。 

在研究该问题的历史中，counting to sampling 技术是一项基本的处理技术：该技术可以将 partition function 计算问题转化为若干相似的采样问题，其中每个采样问题形如询问某点在图上的随机独立集中出现的概率。对于每个采样问题，使用标准的 MCMC 采样方法，我们就可以获得一个时间复杂度为  的采样算法使得每个采样问题的误差在  量级，这可以直接引出一个时间复杂度为  的原问题 FPRAS 算法。

之前的工作证明了当  时  并且在  给出了解决  问题的  的 FPRAS 算法。在本次报告中，王家恒博士简要叙述了他在这个问题解法改进上的主要成果：

1）在  问题下，提出了新的 FPRAS 方案，其在  时拥有亚二次时间复杂度（之前最优是  ）。

2）在一般的 spin system 的情形中，若输入图  是多项式增长的（即一个点能在  步内访问到的点是  ），那么存在一个亚二次时间复杂度的 FPRAS 算法。

该项工作的基础是 Weitz 算法。Weitz 算法可以将一个一般图  转化为一棵树  使得 partition function 不变，但是这个树  的大小可能是指数大的。注意到存在一个线性时间的算法计算一棵树的 partition function（通过自底向上的动态规划），因此一个直观的做法是裁剪这棵树控制时间复杂度，同时以某种方式限制误差。于是，令  为方程  的根，我们可以将树  在高度  处截断并在截断处任意赋值，然后计算整棵树的 partition function，这样算法的时间复杂度为  。在此基础上继续优化，我们不再在截断处任意赋值而是选择在截断处使用 Lazy marginal sampler 方法估计边缘概率，使得在保持相同精度的同时大大降低截断高度。经过精细的计算和新的采样方法的使用，该算法可以达到时间复杂度  。当问题从  扩展到一般的 spin system 后，保持目前算法框架的不变，需要设计策略以

1. 选择适合的边界  ；

2. 在正确的边缘分布下采样；

3. 聚合采样以形成估计器。

在这些方面，王家恒博士简要地说明了使用的技术和达到的结果。

论文：https://arxiv.org/abs/2306.14867

报告：https://pw384.github.io/assets/slides/subquadratic.pptx

合影留念

图文 | 陆宇暄