FOCS 2022 游记

很幸运地去丹佛参加了今年的FOCS！今年FOCS有很多神仙文章，甚至被一些大佬称作“可能是近些年来最强的FOCS program”了。我同时也参加了cls和Roei举办的New Directions in Derandomization Workshop。这篇博客会记录一些我觉得很有意思的文章和talk！

Fast Deterministic Fully Dynamic Distance Approximation

这篇文章给出了完全动态的$(1+\epsilon)$-近似最短路算法。在这里我只讨论他们的main result：我们可以在最坏$O(n^{1.407}\epsilon^{-2}\log(1/\epsilon))$的修改时间和询问时间内，确定性地维护两个点之间的$(1+\epsilon)$-最短路。

由于这篇文章（以及前人的工作）的技术是基于多项式矩阵动态求逆的，所以做到确定性数据结构是一个很了不起的事情。具体地说，这类最短路数据结构一般是基于如下的性质：设$x$为一个变量，$A$为图的邻接矩阵，考虑矩阵$(I-Ax)^{-1}$。（$I-Ax$这个矩阵就是说对角线上的元素都是$1$，图中的边对应的元素都是多项式$-x$，其他地方都是$0$。）通过简单的代数，我们有

\[(I-Ax)^{-1} = \sum_{k=0}^{\infty}(Ax)^k.\]

从上面的式子可以看出，$(I-Ax)^{-1}$这个矩阵包含了关于图的路径的所有信息。具体地说，对于$u,v\in V$，$(I-Ax)^{-1}_{u,v}$是一个形式幂级数，其第$x^k$项系数恰好就是$u$到$v$的长度为$k$的路径条数。这是什么意思呢？如果我们想要动态维护最短路信息，我们只需要利用已有的动态矩阵求逆算法维护$I-Ax$的逆就行了。

现在的问题是：$I-Ax$是个多项式矩阵，而操作多项式的复杂度比操作整数（显然）要高一些。假设我们只关心不超过$k$的距离，那么每个多项式的度数不超过$k$，且系数大小是$O(n^k)$的。这意味着多项式的基本操作（例如加法或乘法）需要$O(k^2\log n)$的时间。前人的工作会使用随机算法：假设我们把所有系数对$p$取模，其中$p$是一个大小大约为$O(n)$的随机质数。如果取模后系数是$0$，那么我们直接假设取模前系数也是$0$（如果$p$选得不好的话，这个假设可能是错的）。这样，多项式的系数大小变成了$O(n)$，每次操作只需要$O(k\log n)$的时间了。可以看出这个随机取模有点像PIT，学术界普遍认为这样的技术是很难去随机化的。因此，对于使用多项式矩阵求逆技术的数据结构问题来说，确定性的数据结构有着重要的意义。

这篇文章有一个很酷的insight：如果我们要维护$(1+\epsilon)$-近似最短路的话，我们只需要维护值不超过$O(1/\epsilon)$的精确最短路就行了！动态矩阵求逆的复杂度是一次修改/询问可以做到$O(n^{1.407})$次“操作”；这里，我们每次操作是$k=1/\epsilon$的多项式加法/乘法。所以，用上述（暴力的）确定性算法维护的话，复杂度是$O(n^{1.407}\epsilon^{-2}\log(1/\epsilon))$。

这篇文章酷的地方在于：如何将$(1+\epsilon)$-近似最短路规约到值不超过$O(1/\epsilon)$的精确最短路？答案是使用emulator！（这个规约倒是很组合，没有用到什么矩阵乘法。。。）假设我们有一张图$G$，以及一张稀疏图$H$使得对任意$u,v$，$d_G(u,v) \le d_H(u,v)\le (1+\epsilon/2)d_G(u,v)+4$，那么我们称$H$为$G$的emulator。我们想求$G$中的点$u$到$v$的$(1+\epsilon)$-最短路的话，只需要做如下操作就行了：

• 首先，在$H$中求$u$到$v$的最短路。这一步的复杂度是$O(|H|)$的，本文中$H$的边数是$O(n^{4/3})$所以不是瓶颈。如果$d_G(u,v) > O(1/\epsilon)$，那么$(1+\epsilon/2)d_G(u,v)+4\le (1+\epsilon)d_G(u,v)$，所以这一步能cover掉$d_G(u,v)$较大的情况。
• 其次，假设$u$到$v$的最短路不超过$O(1/\epsilon)$，求其精确最短路。这一步的复杂度是动态矩阵求逆的复杂度（$O(n^{1.407})$）。这一步cover的是$d_G(u,v)$较小、且上面那个$+4$的项会很重要的情况。

于是，对于动态图算法而言，我们除了动态维护不超过$O(1/\epsilon)$的最短路以外，还需要动态维护一个emulator。关键的insight在这里：某些emulator的构造方式只需要知道不超过$O(1/\epsilon)$的最短路！所以我们维护了不超过$O(1/\epsilon)$的最短路之后再动态模拟那些emulator的构造方式即可。

最后说一些这篇文章的缺点吧。第一，这篇文章只做到了无向无权图。理论上，对于$(1+\epsilon)$-近似最短路来说，无权图和带权图的复杂度区别应该不大。但是这篇文章的emulator的构造方式只对无权图管用。带权图的话也有对应的构造方式，但是可能不仅仅需要知道不超过$O(1/\epsilon)$的最短路了，而是需要知道一些更复杂的信息，所以这篇文章的方法没法直接构造。不过关于这个问题在有向图上能不能做到更好，我没有什么见解。。。第二，这篇文章不支持path-reporting（就是询问只能给你一个数，表示近似距离，而不能给你一条具体的近似最短路）。这些使用多项式矩阵求逆的数据结构普遍地无法做path-reporting（我最喜欢的例子是这个），我感觉这也是个大的研究问题。。。