RANDOM 2022 游记

r_64 posted @ 2022年9月10日 15:54 in 未分类 , 234 阅读

刚刚注册了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}$电路即可,但是我们并没有确定性的算法来构造这些电路。。。

Unbalanced Expanders from Multiplicity Codes

设$C:\{0, 1\}^n \times \{0, 1\}^d \to \{0, 1\}^m$为一个函数。我们说这个函数是一个$(n, k)\to_\epsilon (m, k')$-凝结器(condenser),如果对任意的最小熵(min-entropy)至少为$k$的分布${\cal X}$,$C({\cal X}, {\cal U}_d)$和某个最小熵至少为$k'$的分布的距离不超过$\epsilon$(其中,${\cal U}_d$为一个均匀随机的长度为$d$的种子串)。如果$k+d = k'$,那么我们说这个函数是一个无损凝结器(lossless condenser)。GUV构造出了一个不错的(目前最好的?)无损凝结器,本文的贡献是用完全不同的技术构造出了一个参数一样的凝结器。

凝结器和纠错码之间有紧密的联系。设$C(-, -)$是一个凝结器,那么$\{(C(f, 1) ... C(f, 2^d))\}_{f \in \{0, 1\}^n}$也是一个好的纠错码。Parvaresh-Vardy code和Multiplicity code是两个拥有很好的列表解码(list-decoding)参数的纠错码,GUV的凝结器就是基于Parvaresh-Vardy code的;本文用和GUV类似的构造把Multiplicity code变成了一个很好的凝结器。据说背后的分析和GUV长得完全不同。

虽然我并看不懂,但是来都来了,至少还是得把两个凝结器的构造讲一下。GUV(或者说,Parvaresh-Vardy code)构造是这样的:令$\mathbb{F}$为一个有限域,$C:\mathbb{F}^n \times \mathbb{F} \to \mathbb{F}^{s+2}$。$C$的第一个输入为度数小于$n$的多项式$f$,第二个参数(“种子”)为域中的元素$a$,选一个参数$h$,定义

\[C(f, a) = (a, f(a), f^h(a), f^{h^2}(a), \dots, f^{h^s}(a)).\]

本文(或者说,Multiplicity code)把上式改成了:

\[C(f, a) = (a, f(a), f^{(1)}(a), f^{(2)}(a), \dots, f^{(s)}(a)).\]

其中$f^{(i)}$表示对$f$求$i$阶导。

 

 


登录 *


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