上海交大研究团队在计算机科学领域顶级会议STOC’24上发表图着色采样研究进展

　　

近日，电子信息与电气工程学院约翰·霍普克罗夫特计算机科学中心博士生王玉林、副教授张驰豪和日本国立信息学研究所在读博士生张子涵合著的论文 “Sampling proper colorings on line graphs using (1+o(1))Δ colors”（如何在线图上使用(1+o(1))Δ种颜色采样合法着色）被计算机科学领域顶级国际会议第56届ACM计算理论研讨会（STOC 2024，56th Annual ACM Symposium on Theory of Computing）接收。张子涵是上海交通大学2023届本科毕业生，该论文的主要结果也是其本科毕业设计内容。

论文内容

对无向图的合法着色进行采样是近似计数与采样领域内的重要公开问题。关于这个问题的主要猜想是，对于最大度数为 Δ 的图类，当颜色数满足 q>Δ+1 的时候，一类称之为 single-site Glauber dynamics 的马尔可夫链可以在多项式时间内收敛，因此蕴含了高效的采样以及近似计数算法。然而，分析这样一类马尔可夫链的收敛速度在技术上是相当困难的。目前最好的结果需要的条件是 q>1.84Δ，距离猜想中的 q>Δ+1 还有很大的距离。

本篇论文研究了该问题的一类非常重要的特殊情况，即当我们关心的图是线图（line graphs）时，single-site Glauber dynamics 的快速收敛条件。线图上的着色实质上等价于对图的边进行着色（edge coloring），这是一类常见的组合问题。论文证明了当 q=(1+o(1))Δ 的时候，该马尔可夫链即快速收敛。此结果大大改进了之前最好的 q>1.67Δ 的条件，也十分接近于 q>Δ+1 的猜想。

证明的方法基于近年来发展的谱独立（spectral independence）技术。谱独立被认为是一个正确的刻画了高维数据相关性的概念，它的引入推广了高维数据集上的一些泛函不等式，而后者蕴含了相关马尔可夫链的快速收敛性。本论文发展了最近提出来的一种建立谱独立性质的被称之为矩阵下渗定理（matrix trickle-down theorem）的技术，通过归纳的方式，证明了在线图上合法着色集合的谱独立上界。

论文链接：https://arxiv.org/abs/2307.08080

关于STOC

ACM计算理论年会（STOC）是理论计算机科学领域最顶级的国际会议，在整个计算机科学领域享有崇高的声望，属于公认难度最高的会议之一。该会议由ACM中的算法和计算理论兴趣小组（Special Interest Group in Algorithms and Computation Theory，SIGACT）提供资助，历年会议涵盖的领域十分广泛，包括算法和数据结构、计算复杂性、密码学、计算几何、算法图论与组合学、计算随机性、计算博弈论和量子计算等。

作者：

电子信息与电气工程学院

供稿单位：

电子信息与电气工程学院