STOC 2023 游记

r_64 posted @ 2023年6月25日 01:56 in 未分类 , 302 阅读

去佛罗里达开了STOC玩了玩ww

A Borsuk-Ulam lower bound for sign-rank and its applications

我试图用通信复杂度的语言来描述一下这篇文章的结果。这篇文章给出了一个部分函数(partial function)$f$,使得$f$的公共随机数(public coin)通信复杂度是$O(1)$,但是无限制(unbounded error)私有随机数(private coin)通信复杂度是$\Omega(\log n)$。

首先介绍一下公共随机数通信复杂度(${\rm R}^{\rm pub}$)和无限制私有随机数通信复杂度(${\rm U}^{\rm priv}$)。在随机通信复杂度中,我们希望得到正确答案的概率大于$1/2$。一般来说,我们会希望这个概率远大于$1/2$(比如说大于$2/3$),于是我们就能够得到一般的随机通信复杂度(${\rm R}$)。但是在某些时候,我们会考虑概率稍稍大于$1/2$的情况(比如说,这个概率有可能是$1/2 + 2^{-n}$),于是我们得到了无限制随机通信复杂度(${\rm U}$)。此外,根据Alice和Bob是使用相同的随机串还是互相独立的随机串,我们会有公共随机数和私有随机数的区别。

显然,公共随机数通信复杂度${\rm R}^{\rm pub}$不会超过私有随机数通信复杂度${\rm R}^{\rm priv}$。这是因为Alice可以只看前一半随机串,Bob可以只看后一半随机串。Newman证明了${\rm R}^{\rm priv}_{\epsilon + \delta}(f) \le {\rm R}^{\rm pub}_\epsilon(f) + O(\log n + \log (1/\delta))$,也就是说私有随机数通信不会比公共随机数通信高太多。在无限制的情况下,任何函数的公共随机数无限制通信复杂度都不超过$2$,因此我们只考虑私有随机数。本篇文章的结果是:存在一个部分函数,其${\rm R}^{\rm pub}$是常数,但是${\rm U}^{\rm priv}$至少是$\Omega(\log n)$。(于是,这个结果也表明了Newman的结果是紧的。)

本文中考虑的函数是Gap Hamming Distance。对于$x,y\in\{-1, 1\}^n$,

\begin{align*}
{\sf GHD}(x,y) = \begin{cases}
1 & \langle x,y\rangle > 0.9n;\\
-1 & \langle x,y\rangle < -0.9n;\\
* & \text{otherwise}.
\end{cases}
\end{align*}

显然,这个函数的${\rm R}^{\rm pub}$是常数。Alice和Bob随机选取常数个位置$i$,然后检查$x_i$是否等于$y-i$即可。这个函数的${\rm U}^{\rm priv}$也不超过$O(\log n)$。Alice随机选取$i$,然后把$i$告诉Bob(注意到因为这里是私有随机数,所以Alice不得不把$i$传输给Bob),双方检查$x_i$是否等于$y_i$即可。这篇文章证明了上述计算${\sf GHD}$的${\rm U}^{\rm priv}$协议是最优的!

上面的结果也可以用矩阵(sign-rank vs margin)或者机器学习(支持向量机)的语言描述,这里略去。

前人证明${\rm U}^{\rm priv}$的下界的方法都也能够证明${\rm R}^{\rm pub}$的下界,所以这篇文章需要新的方法。这篇文章使用了一些拓扑学的技术(Borsuk-Ulam定理)。首先,假设我们想证明$d$维球面($\mathbb{S}^{d-1}$)上的${\sf GHD}$的sign-rank至少是$d$,也就是不存在$\phi, \psi:\mathbb{S}^{d-1} \to \mathbb{S}^{d-2}$使得对任意$x,y\in\mathbb{S}^{d-1}$,有\[\mathrm{sign}(\langle \phi(x), \psi(y)\rangle) = \begin{cases}1&\langle x, y\rangle > \gamma,\\-1 & \langle x,y\rangle < -\gamma.\end{cases}\]简单起见假设$\phi$是连续的。那么由Borsuk-Ulam定理,存在$x\in\mathbb{S}^{d-1}$使得$\phi(x) = \phi(-x)$。选取$y$使得$\langle x, y\rangle > \gamma$,那么$\langle \phi(x), \psi(y)\rangle > 0$。与此同时,$\langle -x, y\rangle < -\gamma$,因此$\langle \phi(-x), \psi(y)\rangle < 0$,这与$\phi(x) = \phi(-x)$矛盾。对于$\phi$不是连续的一般情况,文章用了一些方法把$\phi$“变得连续”并证明了相同的结果。布尔的情况($\{-1, 1\}^n$而不是$d$维球面)貌似可以规约到球面的情况,我没有看懂(。。。)

Towards the Erdős-Gallai Cycle Decomposition Conjecture

Erdős-Gallai猜想是指如下的猜想:任意一个$n$个点的无向图可以被分解成$O(n)$个简单环(cycle)和$O(n)$条边的不交并。等价地说,如果这张图的每个点的度数都是偶数,那么它可以被分解成$O(n)$个简单环的不交并。本文证明了任意一个$n$个点的无向图可以被分解成$O(n\log^* n)$个简单环和边的不交并。在此之前最好的bound是$O(n\log\log n)$。

本文实际上证明了如下更强的结论:任意一个$n$个点、$d\cdot n$条边的无向图可以被分解成$O(n)$个简单环和$n\cdot\mathrm{polylog}(d)$条边的不交并。如果我们把剩下的那$n\cdot\mathrm{polylog}(d)$条边当成一条新的图(平均度数为$\mathrm{polylog}(d)$),并一次次地使用该结论,那么在$O(\log^\star d)$次之后我们将会得到$O(n\log^\star d)$个环和$O(n)$条边。

这篇文章需要用到一种特殊的expander decomposition。一般来说我们说一个图是expander,如果对任意点集$U$(其中$|U| \le (2/3)n$),$|N(U)| \ge \alpha\cdot U$,其中$\alpha$是某个大于$1$的参数。因为一些(我还没搞明白的)原因,本文中必须考虑所谓的“sublinear expansion”,其中$\alpha = \varepsilon/\log^2 n$小于$1$。这样的sublinear expansion比较弱,所以除此之外本文还需要考虑一种更强的robust sublinear expansion(Def 11):给定参数$s$,对任意大小不超过$2n/3$的点集$U$,任意删掉$s|U|$条边之后,$U$的邻居个数仍然至少是$|U|\cdot (\varepsilon/\log^2 n)$。这种robust sublinear expansion能够推出如下类似superlinear expansion的结论(Prop 12):对任意$U,d$,

  • 要么$|N(U)|\ge s|U|/2d$(这种情况是superlinear expansion),
  • 要么存在$|U|\cdot(\varepsilon/\log^2 n)$个邻居$N'\subseteq N(U)$,使得每个$N'$内的邻居都和$d$个$S$中的点相邻(这种情况是sublinear expansion的强化版本)。

本文详细研究了这类robust sublinear expander,并证明了若干性质(下文中的“expander”默认指“robust sublinear expander”):

  • Expander decomposition(Lemma 14):任意一张图在删掉$4sn\log n$条边之后都能够被分成若干个$(\varepsilon, s)$-expander的并,且这些expander总共占用的点数不超过$2n$。(一个点可以在多个expander中)
  • Subsampling(Lemma 15):假设$G$是一个expander,考虑把$G$的每条边(独立地)以某个概率保留下来,得到一个子图$H$,那么$H$大概率也会是一个(稍弱一些的)expander。作者说这个lemma非常有用,虽然我没有听明白是怎么用的(
  • Routing(Thm 16):任意给出一些点对$\{(s_i, t_i)\}$,我们都可以用很短的路径来连接所有的$s_i \leftrightarrow t_i$,并且这些路径的边是不交的。Thm 16实际上证明了更强的结论——如果我们随机指定大小约为$|V|/3$的点集$V'$,那么我们甚至可以保证这些路径的中间节点都在$V'$中。
  • Sparsifier(貌似是Lemma 20):每个expander都有一个也是expander的稀疏子图。

现在,假设有一张图,我们想把它分解成$O(n)$个简单环和$n\cdot \mathrm{polylog}(d)$条边。首先,我们把这张图分解成若干个expander的并,于是我们只需要把每个expander分解成环和边即可。考虑一个expander $G$,我们找到其sparsifier $H$,并将$G-H$分解成$O(n)$个路径和简单环的并。(如果允许路径的存在而不是只允许环的话,这件事情被Lovasz证明是可以做的。)接下来需要利用$H$把所有路径都连成环,也就是假设$G-H$的分解中的路径集合是$\cal P$,你需要在$H$中找一些很短的路径把$\cal P$中每一条路径的两个端点都连起来。(这一步貌似会出一些问题,比如说你需要保证你在$H$中找到的路径和$\cal P$不交。这个时候需要使用Thm 16中“更强的结论”及一些其他技巧。)最后我们还剩下$H$中的一些边没有用上,因为$H$是稀疏的,所以我们直接把它们丢掉即可。

感觉robust sublinear expander的很好的性质(尤其是decomposition和routing)在算法中应该会有更广泛的应用!

Local and global expansion in random geometric graphs

我们说一个图是2维expander(2DX),如果对任意点$v$,它的邻居的导出子图($G[N_v]$,也叫做$v$的“link”)都是一个expander。所谓的Trickling-down定理指的是:如果这些局部的导出子图有足够好的expansion,那么整个图在全局上也是一个expander。构造2DX和高维expander(HDX)是理论计算机中近年来很重要也很火热的话题。事实上,一个随机(Erdős–Rényi)的稀疏图大概率是一个expander,但是大概率不是一个2DX,因为每个点的邻居都不是很连通(比如说,很有可能这些邻居之间什么边都没有)。

这篇文章的目标是:找一个随机图的模型,使得其中的图大概率是一个2DX。前人给出的模型都需要度数至少是$\Omega(\sqrt{n})$才能保证得到2DX,但是这篇文章做到了任意小的多项式度数($n^\varepsilon$)。模型如下(称作geometric graph):在球面$\mathbb{S}^{d-1}$上随机选取$n$个点$u_1, u_2, \dots, u_n$,当两个点满足$\langle u_i, u_j\rangle \ge \tau$的时候将它们相连,否则就不相连。这里,我们有两个参数$\Delta=n^\varepsilon$(度数)和$d$(球面的维度);$\tau$可以由$\Delta$和$d$计算出来。文章证明了当$\varepsilon$是常数且$d=O(\log n)$的时候,我们大概率能够得到一个2DX。

一些open problem:(1)能不能把这篇文章的结论推广到更高维的HDX上去?(2)能不能确定性地构造一个$\mathbb{S}^{d-1}$上的点集,使得我们能够得到一个2DX?

 


登录 *


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