RANDOM 2022 游记

刚刚注册了RANDOM 2022！因为是线上会议所以只要$10注册费。今年RANDOM看上去有挺多很好玩的paper，打算开会的这几天听一听，然后写点笔记。（因为最近关注算法关注得少了，重心可能更加偏向于复杂度理论，所以主要会去RANDOM，可能不太会去APPROX了。。。

Communication Complexity of Collision

Collision指的是如下问题。有$N$个整数$x_1, x_2, \dots, x_N\in[N]$，要求判断如下两种情况中哪一种发生。

• 情况$1$：$x_1, x_2, \dots, x_N$互不相同。
• 情况$2$：$x_1, x_2, \dots, x_N$包含$N/2$个互不相同的数，每个数出现恰好两次。

如果我们要研究Collision的通信复杂度，我们需要定义如何把输入分给Alice和Bob。假设$N=2^n$且$n$为偶数，我们可以这样分配输入：Alice拿到所有$x_i$的前$n/2$位，Bob拿到所有$x_i$的后$n/2$位。之后，Alice和Bob需要通过通信来求出上述的两种情况中到底哪一种发生了。

本文证明了Collision的量子通信复杂度至少是$\Omega(N^{1/12})$，是这个问题的随机/量子通信复杂度的第一个多项式下界。证明思路如下：首先，我们知道Collision的近似度数（approximate degree）至少是$\Omega(N^{1/3})$。于是，我们可以使用提升定理（lifting theorem）来证明：如果把Collision函数和一个特定的函数$g$（“gadget”）合并起来，那么得到的函数$\text{Collision}\circ g$的量子通信复杂度至少是$\Omega(N^{1/3})$。但是，因为$g$是一个人为构造的函数，所以我们还需要找到$\text{Collision}\circ g$的通信复杂度和Collision本身的通信复杂度之间的关联。对于“长得漂亮”的$g$，这篇文章给出了一个从$\text{Collision}\circ g$到Collision本身的通信复杂度规约！这个规约的复杂度和$g$的大小有关，文章中使用的$g$大小为$4$，所以最终的复杂度下界变成了$\Omega((N^{1/3})^{1/4}) = \Omega(N^{1/12})$。

基于这个结论，本文证明了鸽笼原理的通信复杂度也很高。鸽笼原理是这样的问题：有$2N$个整数$x_1, x_2, \dots, x_{2N}\in[N]$，Alice拿到了所有数的前$n/2$位，Bob拿到了所有数的后$n/2$位，双方希望找到$i, j\in[2N]$使得$x_i = x_j$。（注意：这里考虑的是弱化版的鸽笼原理，我们的范围是$[N]$但是有$2N$个数。最强的鸽笼原理中，我们有范围是$[N]$但是只有$N+1$个数；这种鸽笼原理的下界已经被前人证明了。）本文把Collision的通信复杂度规约到了鸽笼原理的通信复杂度，于是也证明了鸽笼原理的通信复杂度至少是$\Omega(N^{1/12})$。这个结果对于鸽笼原理的证明复杂度（proof complexity）也有一些推论。

Open problem：我问了文章作者如果鸽子数量比笼子数量多很多的话，有没有令人满意的复杂度下界。（例如有$N^2$个不超过$N$的整数，而不仅仅是$2N$个，要求找一个collision。）貌似并没有？

Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness

好耶，是Range Avoidance！

这个问题的定义是这样的：给出一个电路$C:\{0, 1\}^n \to \{0, 1\}^\ell$，其中$\ell > n$，要求找到一个不在$C$的输出范围内的串。（严格的定义就是：找到一个$y\in\{0, 1\}^\ell$使得对任意$x\in\{0, 1\}^n$，$C(x) \ne y$。）根据“对偶鸽笼原理”，我们随机输出一个长度为$\ell$的串就会有$1/2$的正确概率。所以这个问题对随机算法而言是简单的，我们考虑确定性算法。

这篇文章对很多电路类给出了用傅里叶分析解决$\mathscr{C}$-Avoid的算法。设$C:\{0, 1\}^n \to \{0, 1\}^\ell$是一个输入电路，并且假设我们证明了：不论给$C$输入什么分布$\cal X$，输出分布$C({\cal X})$不可能是pairwise independent的，那么我们就能够在${\sf FP}^{\sf NP}_{\|}$解决$C$的Avoid。这是因为我们可以找到$O(\ell^2)$个串使得它们构成一个pairwise independent的分布，如果这$O(\ell^2)$个串都在$C$的输出范围内，那么我们可以造一个${\cal X}$使得$C({\cal X})$的输出恰好是这$O(\ell^2)$个串的均匀分布，矛盾。在找到了这$O(\ell^2)$个串之后，我们可以在${\sf FP}^{\sf NP}_{\|}$内挑出不在$C$的输出范围内的那个串。

对于很弱的电路$C$，如何证明上述结论呢？我们选定一些参数$(d,\delta)$使得不论$C$的输入分布${\cal X}$是什么，$C$都和某个大小为$d$的${\sf PARITY}$有至少为$\delta$的correlation。用一些傅里叶分析的方法可以对${\sf NC}^0_k$电路、常数宽度的CNF/DNF、approximate degree小的函数等电路类求出不错的$(d, \delta)$。这样我们就能得到对应电路类的Avoid算法了。

注意到这篇文章中的算法实际上给出了一个hitting set：我们在看到输入电路$C$之前就选好了${\rm poly}(\ell)$个串，并且保证对任意$C\in\mathscr{C}$，这些串中的某一个将会在$C$的输出范围之外。视频的最后提出了一个问题：对哪些电路类，我们可以造一个hitting set？“造hitting set”这件事情本身也是个explicit construction，它的复杂度如何？（注：如果${\sf E}$需要指数级别的${\sf \Sigma}_2^p$-oracle电路，那么我们可以对${\sf P}_{/{\rm poly}}$造一个hitting set。）

最后挂一个我特别喜欢的Open problem：输入一个从$n$位到$n^{1.01}$位的${\sf NC}^0_3$电路，在${\sf FP}^{\sf NP}$内找到一个不在输出范围内的串。

Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

文章中的“game”指的是如下游戏：有一个主持人和$k$个玩家，主持人从某个分布中随机抽取$(x_1, x_2, \dots, x_k) \in {\cal X}_1\times {\cal X}_2 \times \dots \times {\cal X}_k$。接下来，主持人把$x_i$告诉第$i$个玩家，第$i$个玩家告诉主持人一个值$y_i \in {\cal Y}_i$。玩家之间不能交流；不失一般性假设每个玩家都是一个确定的函数$f_i : {\cal X}_i \to {\cal Y}_i$。最后，主持人计算某个布尔函数$P(x_1, x_2, \dots, x_k, y_1, y_2, \dots, y_k)$，如果$P=1$那么玩家赢了游戏，否则玩家输了。游戏的值${\rm value}({\cal G})$等于所有玩家执行最优策略、主持人随机抽取输入时，$P=1$的概率，也就是：

\[{\rm value}({\cal G}) := \max_{f_1, f_2, \dots, f_k}\Pr_{(x_1, x_2, \dots, x_k)}[P(x_1, \dots, x_k, f_1(x_1), \dots, f_k(x_k)) = 1].\]

举个例子。（事实上这个例子是本文中非常重要的例子，后面会讲。）主持人从${\cal S} = \{(1, 0, 0), (0, 1, 0), (0, 0, 1)\}$中均匀随机地抽取一个元素$(x_1, x_2, x_3)$，并将$x_i$告诉第$i$个玩家。（于是恰好一个玩家收到$1$，其他玩家都收到$0$）。第一个玩家需要回答一个长度为$n$的串$a\in\{0, 1\}^n$，第二个玩家需要回答一个长度为$n$的串$b\in\{0, 1\}^n$，第三个玩家需要回答一个数$i\in[n]$。

• 如果第一个玩家收到了$1$，那么主持人要求$b_i = 0$。
• 如果第二个玩家收到了$1$，那么主持人要求$a_i = 0$。
• 如果第三个玩家收到了$1$，那么主持人要求对每一位$j\in[n]$，都有（$a_j = 1$或$b_j = 1$）。

可以看到这是个很难的游戏。如果某个玩家收到了$1$，那么他知道主持人的要求是什么，但是改变不了游戏的结局；如果某个玩家收到了$0$，那么他可以影响游戏的结局，但是他不知道应该怎么影响（例如多输出$0$还是多输出$1$）。

假设我们有一个游戏，现在考虑将上述游戏并行重复$m$次（parallel repetition），记作${\cal G}^{\otimes m}$：主持人从分布中抽取$m$组输入$\{(x_1^j, x_2^j, \dots, x_k^j)\}_{j\in [m]}$，把每个$\{x_i^j\}_{j\in [m]}$告诉玩家$i$，然后每个玩家$i$产生$m$个回答$\{y_i^j\}_{j\in [m]}$。如果对每个小游戏$j\in[m]$，玩家都赢了这个小游戏（也就是$P(x_1^j, \dots, x_k^j, y_1^j, \dots, y_k^j) = 1$），那么就说玩家赢了整个游戏；否则玩家就输了。很明显，如果玩家按照每个小游戏的最优策略独立地进行每个小游戏，那么玩家赢下整个游戏的概率至少是

\[{\rm value}({\cal G}^{\otimes m}) \ge {\rm value}({\cal G})^m.\]

但是，对于某一些游戏，以上结论并不紧，更聪明的玩家可以做到严格比${\rm value}({\cal G})^m$更优。这个领域的big open problem是说：${\rm value}({\cal G}^{\otimes m})$会随着$m$指数下降（$\le {\rm value}({\cal G})^{\Omega(m)}$），我们没法做到比${\rm value}({\cal G})^m$好太多！

对于一般的游戏而言，我们连反多项式大小的上界（${\rm value}({\cal G}^{\otimes m}) \le 1/{\rm poly}(m)$）都不会证（假设${\rm value}({\cal G}) < 1$）。这篇文章证明了如果有三个玩家（$k=3$），输入是0/1（${\cal X}_i = \{0, 1\}$），那么反多项式大小的下界是成立的。通过一些分类讨论，前人的工作已经证明了大部分这样的游戏有反多项式大小的上界，唯一剩下的情况是这样的：$(x_1, x_2, x_3)$只有$(1, 0, 0)$、$(0, 1, 0)$、$(0, 0, 1)$三种可能性。这篇文章对这个剩下的情况也证明了反多项式上界。

很有意思的一点在于，上面描述的那个游戏对于【输入只有$(1, 0, 0)$、$(0, 1, 0)$、$(0, 0, 1)$三种可能性的情况】是完全的！对任意一个三玩家游戏${\cal G}$，如果输入只有上述三种可能性，那么${\cal G}^{\otimes m}$可以（某种意义上）规约到上述游戏的$m$-parallel repetition。这篇文章接着用傅里叶分析的方法研究了上述游戏，证明了它的反多项式上界。

Affine extractors and AC0-Parity

这篇文章给出了很多现有技术无法证明${\sf IP}\notin {\sf AC}^0\circ{\sf XOR}$的一个原因。这个原因很有意思！

一个函数$f:\{0, 1\}^n \to \{0, 1\}$是一个$(k, \epsilon)$-仿射提取器（affine extractor），如果对于每个维度为$k$的仿射空间（affine space）${\cal A}$，都有$\Pr[f({\cal A}) = 1] \in [1/2 \pm \epsilon]$。${\sf IP}$就是一个很好的仿射提取器。这篇文章发现：很多前人证明${\sf IP}$的${\sf AC}^0\circ{\sf XOR}$下界的技术也适用于一般的仿射提取器！例如，前人证明了深度为$4$的${\sf AC}^0\circ{\sf XOR}$电路需要$\tilde{\Omega}(n^2)$大小才能计算${\sf IP}$；深度为$d$的${\sf AC}^0\circ{\sf XOR}$电路需要$\Omega(n^{1+4^{-d}})$大小才能计算${\sf IP}$。这些下界也适用于（某些参数下）任意的仿射提取器。

仿射提取器的出现其实是非常自然的——很多电路类在仿射限制（affine restriction）下会变小，而仿射提取器是在仿射限制下仍然不会有过多简化的函数。所以，在仿射限制下会变得太小的电路就不能计算仿射提取器了。

这篇文章构造出了仿射提取器的上界。深度为$d$的${\sf AC}^0\circ{\sf XOR}$电路可以在$n^{1+O(4^{-d})}$大小内计算仿射提取器，深度为$4$的${\sf AC}^0\circ{\sf XOR}$电路可以在$\tilde{O}(n^2)$大小内计算仿射提取器。一个美中不足的事情是，深度为$4$的这两个上下界中，仿射提取器的参数好像没有对上。。。另一个美中不足的事情是文章的证明是非构造性的：随机取一个某种形式的${\sf AC}^0\circ{\sf XOR}$电路即可，但是我们并没有确定性的算法来构造这些电路。。。