STOC 2023 游记

去佛罗里达开了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？