FOCS 2022 游记

r_64 posted @ 2022年11月05日 15:58 in 未分类 , 86 阅读

很幸运地去丹佛参加了今年的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(我最喜欢的例子是这个),我感觉这也是个大的研究问题。。。

 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter