2023年9月19日，英国爱丁堡大学的王家恒博士访问北京大学前沿计算研究中心。王家恒博士是北京大学第一届图灵班学生，本次来在静园五院做了题为“Approximate Counting for Spin Systems in Sub-Quadratic Time”的报告。报告由中心助理教授孔雨晴老师主持。

　　
王家恒博士报告现场

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

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

　　之前的工作证明了当λ＞λ_{c}(\delta)时Hardcore(λ,Δ)∈NPHard并且在λ≤λ_{c}(\delta)给出了解决Hardcore(λ,Δ)问题的\tilde{O}(n^{2})的 FPRAS 算法。在本次报告中，王家恒博士简要叙述了他在这个问题解法改进上的主要成果：

　　1）在Hardcore(λ,Δ)问题下，提出了新的 FPRAS 方案，其在λ=o(Δ^{-1.5})时拥有亚二次时间复杂度（之前最优是λ=o(Δ^{-2})）。

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

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

1. 选择适合的边界S；
2. 在正确的边缘分布下采样；
3. 聚合采样以形成估计器。

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

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

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

　　
合影留念