ITCS 2023 游记

r_64 posted @ 2023年1月14日 03:39 in 未分类 , 297 阅读

去MIT参加了ITCS'23!呜呜呜出去开会好舒服认识了好多人听了好多talk

Downward self-reducibility in TFNP

这篇文章给出了一个崭新的理解${\sf PLS}$的角度!文章的结论是:①${\sf PLS}$中有downward self-reducible(DSR)的问题;②${\sf TFNP}$中DSR的问题都在${\sf PLS}$中。②感觉是个很本质的事情,看上去和“$T^1_2$能证明在${\sf TFNP}$中的问题都在${\sf PLS}$中”有一定联系?

②背后的intuition大概是这样的。假设我们有一个search problem $R(x, y)$,使得:(base case)如果$|x|=1$,那么存在$y$使得$R(x, y)$成立;(induction)存在一个DSR,给出任意一个$x$,能够输出一些长度小于$x$的串$x_1, x_2, \dots, x_k$($k={\rm poly}(|x|)$);并且给出这些串的答案(也就是说$y_1, y_2, \dots, y_k$使得$R(x_i, y_i)$成立),我们能够算出$y$使得$R(x, y)$成立。根据(base case)和(induction),我们可以用归纳法证明对任意$x$,都存在$y$使得$R(x, y)$成立。可以看出,这个“证明”对应的计算过程恰好是个${\sf PLS}$。

Is Untrusted Randomness Helpful?

是新的关于随机算法的模型!我们说一个问题$L \in {\sf DPP}(f(n))$,如果有一个多项式时间的随机算法${\cal A}$,使用$O(f(n))$个trusted random bits $R_t$和(多项式个)untrusted random bits $R_u$,并且解决$L$。这个算法可以输出$0,1$或者$\bot$,其中$\bot$表示“我不知道”。所谓“解决$L$”的具体定义是:

  • 如果$R_u$是“好的”,那么${\cal A}$会给出正确结果。形式化地说,对任意$x$,$\Pr_{R_t, R_u}[{\cal A}(x) = L(x)] \ge 3/4$。
  • 如果$R_u$是“坏的”,那么${\cal A}$至少不容易出错。形式化地说,对任意$x$和任意$R_u$,$\Pr_{R_t}[{\cal A}(x) \in \{L(x), \bot\}] \ge 3/4$。

注意到${\sf ZPP} = {\sf DPP}(0) = {\sf DPP}(\log n)$,并且${\sf BPP} = \bigcup_{c\in\mathbb{N}}{\sf DPP}(n^c)$,所以${\sf DPP}$可以看成是${\sf ZPP}$和${\sf BPP}$之间的一种插值。最近大家都在思考有没有比电路复杂度下界更紧的、能够把${\sf BPP}$去随机化的复杂度假设(例如CT21LP22)。或许对于比较小的$f(n)$,我们可以搞一些更弱的假设来把${\sf DPP}(f(n))$去随机化?

这篇文章的主要结果是当空间复杂度受限制的时候,关于${\sf DPL}$的一些结论。Saks-Zhou证明了$O(\log n)$空间的随机算法可以用$O(\log^{3/2} n)$空间的确定性算法来去随机化。在${\sf DPL}$模型中,本文证明了$O(\log n)$空间的随机算法只需要$O(\log n)$个trusted random bits(和无限量的untrusted random bits)就可以去随机化(空间复杂度仍然是$O(\log n)$)。(技术我没有仔细看。)与此同时,${\sf DPL}(1) = {\sf ZPL}$。所以${\sf DPL}(f(n))$也可以看成是${\sf BPL}$和${\sf ZPL}$之间的插值,只是此时我们只考虑$f(n)\le O(\log n)$的情况了。

Matrix multiplication via matrix groups

浅看了一下视频,虽然啥也没看懂但是感觉好酷啊!

故事要从Cohn和Umans提出的一个用群论研究矩阵乘法的思路说起。考虑某个群$G$,它对应一个group multiplication tensor:

\[T_G := \sum_{g, h\in G}x_gy_hz_{gh}.\]

这个tensor的代数复杂度比较小。(据说可以用类似于FFT的方法计算?具体细节可能会涉及一些群表示论?)所以如果我们能够把矩阵乘法对应的tensor

\[\langle n,n,n\rangle := \sum_{i, j, k = 1}^n x_{ij}y_{jk}z_{ki}\]

嵌入$T_G$,那么我们就能够得到矩阵乘法的快速算法。事实上,这个框架可以复现Coppersmith-Winograd类的算法并且至少得到$\omega \le 2.41$。

那么我们需要找什么样的群$G$才能得到最好的矩阵乘法算法呢?前人证明了:如果我们考虑的$G$是交换群,那么我们证不了$\omega < 3$;最近cap set的一些进展表明一类“STPP构造”(?)无法证明$\omega = 2$。这篇文章的结论是:李群也不能用来证明$\omega = 2$;这个问题好像和quasirandom group有关(?)

On Low-End Obfuscation and Learning

现有的iO构造中,就算输入的电路是个很简单的电路(例如$3$-CNF),输出的电路仍然很复杂(比如说至少是${\sf NC}^1$的)。这篇文章研究的是:什么时候输入一个很简单的电路时,iO的输出也是一个很简单的电路?这篇文章中有一个有意思的反例:如果单向函数存在的话,那么输入是$3$-CNF的时候,输出不可能也是$O(1)$-CNF。事实上,如果输出电路类的对偶类是PAC-learnable的,那么单向函数就不存在。反过来,输入是$2$-CNF的时候,我们可以做到非常完美的iO(iO算法是确定性的,且找到一个“canonical”的与输入$2$-CNF等价的$2$-CNF)。这个差距感觉和“$3$-${\rm SAT}$是${\sf NP}$-完全的,但是$2$-${\rm SAT}$很容易”有关。

文章中有个很有意思的问题:找到一个尽量小的电路类$\mathscr{C}$,使得我们的iO输入$3$-CNF的时候能够输出$\mathscr{C}$中的电路。我感觉这个电路类会是个很本质的东西。。。此外我隐隐约约觉得这个topic和meta-complexity有点关系。。。。(作者会去Simons,好耶!

New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method

这篇文章提出了一个新的看待Algorithmic Method的角度。${\sf NEXP}\not\subseteq {\sf ACC}^0$可以用如下两步方法证明:

  • 第一步,在${\sf MA}_{{\sf ACC}^0}$中造一个无法被${\sf ACC}^0$计算的问题,其中${\sf MA}_{{\sf ACC}^0}$指的是“Arthur的计算复杂度是${\sf ACC}^0$”的${\sf MA}$。这个其实很像我们之前就会证的${\sf MA}$复杂度下界(BFT98San09),不同之处在于我们只需要diagonalize against ${\sf ACC}^0$,但同时也要把Arthur的复杂度压到${\sf ACC}^0$。这一步会用到一个新的${\sf PSPACE}$-完全问题,它的各种自规约都能够在${\sf AC}^0[2]$中完成。
  • 第二步是对${\sf MA}_{{\sf ACC}^0}$进行无条件的去随机化。更一般地,如果我们有一个电路类$\mathscr{C}$的非平凡的${\rm CAPP}$算法,那么${\sf MA}_{\mathscr{C}}$可以无条件去随机化。例如,对于${\sf ACC}^0$而言,我们的算法能在$2^{n-n^\epsilon}$时间内求出$2^{n^\epsilon}$大小的${\sf ACC}^0$电路的${\rm CAPP}$,那么这就对应着quasipoly time derand,也就是${\sf MA}_{{\sf ACC}^0} \subseteq \textsf{i.o.-NQP}$。
  • 总结一下就是:首先,我们在${\sf MA}_{{\sf ACC}^0}$中构造出一个对${\sf ACC}^0$困难的问题$L$,然后利用${\sf ACC}^0$的性质把$L$去随机化得到问题$L'$,那么$L' \in {\sf NQP}$。并且,$L'$和$L$在无穷多个输入长度上是等价的,所以$L'$对${\sf ACC}^0$也是困难的。

个人认为这样思考Algorithmic Method最大的好处是不需要管Easy Witness Lemma了。对任意${\sf NEXP}$机器$M$和任意输入$x$,如果$M$接受$x$,那么根据${\sf NEXP}$的定义我们知道存在一个长度为$2^{{\rm poly}(n)}$的$y$使得$M$在非确定选择为$y$的时候会接受$x$。所谓的Easy Witness Lemma(下称EWL)指的是:如果${\sf NEXP}\subseteq {\sf P}_{\rm /poly}$,那么对任意$x$,存在一个多项式大小的电路$C$使得当$M$的非确定选择$y$等于$C$的真值表的时候,$M$会接受$x$。简单地说,如果${\sf NEXP}$有“easy circuit”,那么${\sf NEXP}$有“easy witness”。

EWL虽然很优美,但是不是很好理解。举个例子,令$C'$为解决${\sf NEXP}$完全问题的电路,上述描述中的$C$和$C'$之间的关系其实并不明朗(例如我们不知道怎么从$C'$构造出$C$)。这是因为EWL的证明分为两步——第一步先在${\sf MAEXP}$中造了一个电路复杂度很高的问题$L$,第二步假设${\sf NEXP}$没有“easy witness”,我们就能用hard witness把$L$去随机化到${\sf NEXP}$中。EWL曾经是Algorithmic Method的瓶颈,例如Murray-Williams需要证明一个更强的EWL才能把${\sf NEXP}\not\subseteq {\sf ACC}^0$改进到${\sf NQP}\not\subseteq {\sf ACC}^0$,cls需要证明一个“unary average-case EWL”才能把上述复杂度下界改进为平均复杂度下界。所以,一个不需要EWL的证明框架可以帮助我们更好地理解整个Algorithmic Method的证明结构。(这个框架和原来的证明是等价的,所以这个框架其实是在帮助我们理解EWL,笑。)EWL的本质是“我们有无条件的${\sf MA}$复杂度下界,所以我们应该用hard witness把${\sf MA}$去随机化”。本文的新的角度或许能够帮我们搞出更好的EWL(比如说平均复杂度下的EWL)?

On Oracles and Algorithmic Methods for Proving Lower Bounds

Ryan在视频里说这篇文章是“两篇sub-paper”,所以我也写两个sub-笔记(

第一篇sub-paper研究了missing string问题:给出长度为$n$的字符串$x_1, x_2, \dots, x_m$,其中$m < 2^n$,要求找出一个不等于任何$x_i$的串。这个问题可以看成range avoidance问题(Korten21RSW22)的“黑盒”形式:给出一个函数$C:\{0, 1\}^{\log m} \to \{0, 1\}^{n}$(但是只能黑盒访问这个函数),求$C$的一个non-output。这个问题有一个很显然的线性时间算法,所以值得研究的问题应该是:更低的复杂度类能不能解决这个问题?

这篇sub-paper的结论之一是:missing string有较小的${\sf AC}^0_{k+1}$电路当且仅当对任意$A$,$\Sigma_k{\sf E}^A\not\subseteq\textsf{i.o.-Size}^A[2^n/n]$,也就是我们能够对$\Sigma_k{\sf E}$证一个relativizing的极大($\sim 2^n/n$)的电路复杂度下界。当$k=1$时,两者都是假的(存在一个oracle $A$使得${\sf NEXP}^A\subseteq{\sf P}^A_{\text{/poly}}$);当$k\ge 3$时,两者都是真的(对任意$A$,$\Sigma_3{\sf E}^A\not\subseteq\textsf{i.o.-Size}^A[2^n/n]$)。所以最有意义的情况是$k=2$:我们知道$\Sigma_2{\sf E}\not\subseteq{\sf P}_{\text{/poly}}$,但是我们不知道这个类有没有$2^{\Omega(n)}$的下界。根据这篇sub-paper,这个问题等价于设计一个解决missing string的${\sf AC}^0_3$电路。

第二篇sub-paper研究了Algorithmic Method。“${\sf NEXP}\not\subseteq {\sf ACC}^0$”肯定是non-relativizing的,因为${\sf NEXP}\subseteq {\sf P}_{\text{/poly}}$的那个oracle world中,${\sf NEXP}$实际上可以被极其简单(比${\sf ACC}^0$还要简单)的电路计算。但是,${\sf NEXP}\not\subseteq {\sf ACC}^0$是由“Algorithmic Method”证出来的,后者说的是如果我们有一个电路类的分析算法(${\rm SAT}$或${\rm CAPP}$),那么我们能够证明这个类的电路复杂度下界。现在问题来了:这个从分析算法到复杂度下界的“Algorithmic Method”是不是relativizing的?这篇sub-paper给出了两个oracle:

  • 在第一个oracle world中,${\sf EXP}^{\sf NP}\subseteq {\sf P}_{\text{/poly}}$,但是${\rm CAPP}$有确定性多项式时间的算法。也就是说,在这个oracle world中,虽然电路分析算法(${\rm CAPP}$)存在,但是我们证不了电路复杂度下界。于是${\rm CAPP}$-Alg method不是relativizing的。
  • 在第二个oracle world中,${\sf EXP}\subseteq {\sf P}_{\text{/poly}}$,但是${\rm SAT}$有一个次半指数(sub-half-exponential,也就是$h$使得$h(h(n))\ll 2^n$)时间的算法。次半指数时间是紧的——Appendix B证明了,如果这个${\rm SAT}$算法再快一点点的话,那么我们就可以用relativizing proof证明${\sf EXP}\not\subseteq {\sf P}_{\text{/poly}}$。这说明relativizing ${\rm SAT}$-Alg method无法用来证明${\sf EXP}$的电路复杂度下界。很可惜这个oracle并没有排除用relativizing ${\rm SAT}$-Alg method证${\sf {\color{red}N}EXP}$电路复杂度下界的可能性。

值得关注的是,第二个oracle证实了某个问题的答案恰好是次半指数函数。这种函数经常出现在复杂度理论中,比如说很多复杂度类的最好的电路复杂度下界是次半指数函数。然而,我们之前并没有oracle result说明次半指数是“正确的”答案。

On Flipping the Fréchet distance

Fréchet距离,又称遛狗距离(确信),是一种测量两条曲线之间“距离”的度量。假设你要从一条曲线$P$的起点走到终点,你的狗子要从另一条曲线$Q$的起点走到终点,问:你至少需要多长的绳子把狗子牵住?这个距离就叫做$P$和$Q$的遛狗距离

Fréchet distance

为了定义“翻转遛狗距离”,我们先写出遛狗距离的表达式。假设人和狗都在某个度量空间$\cal X$中(你可以直接假设${\cal X}=\mathbb{R}^2$是欧式平面)。给出两条曲线,也就是两个连续函数$P,Q:[0,1]\to {\cal X}$,人和狗走路的策略可以看成是两个连续函数$x_{\text{人}}:[0, 1] \to [0, 1]$和$x_{\text{狗}}:[0, 1] \to [0, 1]$,代表着时间$t$的时候,人走到了点$P(x_{\text{人}}(t))$,狗走到了$Q(x_{\text{狗}}(t))$。除了连续性以外,我们显然还得要求$x_{\text{人}}(0) = x_{\text{狗}}(0) = 0$,$x_{\text{人}}(1) = x_{\text{狗}}(1) = 1$。那么,$P$和$Q$的遛狗距离,也就是我们需要的绳子的长度就是在$x_{\text{人}}$和$x_{\text{狗}}$满足上述条件的情况下,下式的极值:

\[d_{\text{遛狗}}(P, Q) := \inf_{x_{\text{人}}, x_{\text{狗}}}\sup_{t\in [0, 1]}\|P(x_{\text{人}}(t)) - Q(x_{\text{狗}}(t))\|.\]

遛狗距离是刻画两条曲线近似程度的很有用的度量。很可惜它的计算复杂度是$O(n^2)$的(如果给出的$P$和$Q$都是$n$段的折线的话),而且很可能做不到比$n^{2-o(1)}$更快了。(Bringmann牛逼!

这篇文章中我们考虑“翻转遛狗距离”:

\[d_{\text{covid}}(P, Q) := \sup_{x_{\text{人}}, x_{\text{狗}}}\inf_{t\in [0, 1]}\|P(x_{\text{人}}(t)) - Q(x_{\text{狗}}(t))\|.\]

你可以认为你和你的狗在covid时代需要保持一定的距离,所以你们希望尽量远地完成自己的路线。$d_{\text{covid}}(P, Q)$等于最大的$d$,使得在整个过程中,你们的距离都至少是$d$

这篇文章证明了一维的“翻转遛狗距离”可以在$O(n\log^2 n)$时间内计算,高维的“翻转遛狗距离”也可以在$O(n^2)$时间内计算。此外,这篇文章也给出了一些下界:假设OV猜想是对的,近似计算二维的“翻转遛狗距离”需要$n^{2-o(1)}$时间。

Lifting to Parity Decision Trees via Stifling

这是一篇lifting的文章:令$\mathscr{C}$和$\mathscr{D}$为两个计算模型(一般来说$\mathscr{D}$比$\mathscr{C}$强)。给出一个函数$f$,我们希望造一个函数$h$,使得$\mathscr{D}$中计算$h$的复杂度约等于$\mathscr{C}$中计算$f$的复杂度。也就是说,我们希望让这个增强的计算模型$\mathscr{D}$并没有什么卵用。(捂脸)

一个很常用的构造是所谓的“gadget”。令$g:\{0, 1\}^m \to \{0, 1\}$,其中$m$是一个很小的数(比如说常数),令$h = f\circ g$。更具体地说,如果$f:\{0, 1\}^n \to \{0, 1\}$(也就是说$f$接受$n$个位的输入),那么$h$接受$n\cdot m$位输入。我们把这些输入划分成$x_1, x_2, \dots, x_n \in \{0, 1\}^m$,那么

\[h(x_1, x_2, \dots, x_n) = f(g(x_1), g(x_2), \dots, g(x_n)).\]

为了方便下文讨论,我们令$z \in \{0, 1\}^n$表示原来$f$的输入($f(z)$),在计算$h = f\circ g$的时候有$z_i = g(x_i)$。同时,令$x_{i, j}$为$x_i$的第$j$位。

本文中,$\mathscr{C}$是决策树,$\mathscr{D}$是异或决策树。异或决策树是个比决策树更强的模型,因为它每次可以询问一堆输入位的异或(决策树每次只能问一个位)。本文证明了:如果$g$拥有一种性质(“$k$-stifling”),那么$h$的异或决策树复杂度至少是$f$的决策树复杂度的$k$倍。特别地,如果$g = {\sf MAJ}_3$,那么$h$的异或决策树复杂度至少会不小于$f$的决策树复杂度。

证明很简单。假设$f$的决策树复杂度是$d$。那么,我们有一个adversary ${\cal A}$,使得任给一个只询问$d-1$次的决策树${\cal T}$,${\cal A}$和${\cal T}$交互后会确定下输入$z$的某$d-1$位,并且在此时$f(z)$并没有被确定下来(也就是既可以是$1$又可以是$0$)。现在令$h = f\circ {\sf MAJ}_3$,我们有一个询问$d-1$次的异或决策树${\cal T}_\oplus$(但是${\cal T}_\oplus$的每次询问都是更加复杂的异或询问),我们希望造一个新的adversary来跟${\cal T}_\oplus$交互,并且使得$d-1$次交互之后$h$的值还没有被确定下来。

我们先考虑异或询问会干嘛。设我们的输入为$y \in \{0, 1\}^N$,每个位$y_i$要么是“自由”的,要么等于某些其他$y_j$的异或。假设我们询问$y_{i_1} \oplus y_{i_2} \oplus \dots \oplus y_{i_k}$的值并且这个值等于$b$,那么我们挑出其中某个自由的$y_{i_j}$,不妨设为$y_{i_1}$,然后把$y_{i_1}$赋值成$b \oplus y_{i_2} \oplus \dots \oplus y_{i_k}$。

在模拟${\cal T}_\oplus$的过程中,同样地,某些$x_{i, j}$会是“自由”的,其他$x_{i, j}$等于某些其他位的异或。同时,当某一个$x_{i, j}$变得不再“自由”的时候,我们就顺势把$z_i$确定下来。假设${\cal T}_\oplus$询问了某个$x_{i_1,j_1} \oplus \dots \oplus x_{i_k,j_k}$的值。不失一般性,假设$z_{i_1}$还没有被确定下来,那么我们把$x_{i_1, j_1}$确定为$b \oplus x_{i_2, j_2} \oplus \dots \oplus x_{i_k, j_k}$,其中$b$是这一次询问的答案(随意回答)。接下来,我们询问原来的adversary ${\cal A}$,$z_{i_1}$等于什么?假设$z_{i_1} = b'$,那么我们令$x_{i_1, j'} = b'$(对所有$j' \ne j_1$),此时不论$x_{i_1, j_1}$等于什么,我们都可以保证${\sf MAJ}(x_{i_1, 1}, x_{i_1, 2}, x_{i_1, 3}) = b'$。

可以看到上面的证明有效,恰恰因为${\sf MAJ}_3$满足如下条件:考虑${\sf MAJ}_3$输入的任意一位$i\in[3]$,和任意的$b\in\{0, 1\}$,我们都能确定输入的剩下两位使得不论第$i$位等于多少,输出都等于$b$。(让剩下两位都等于$b$即可。)一个函数$g$是“$k$-stifling”的,当且仅当在对输入的任意$k$位,和任意的$b\in \{0, 1\}$,我们都能够确定$g$剩下的$m-k$个输入使得$g$的输出等于$b$。上面的证明可以很直接地推广到$k$-stifling的情况。

最后,本文的motivation之一是证明复杂度中的open problem:证明一个linear resolution (${\rm Res}(\oplus)$)的下界。这个问题等价于证一个异或决策DAG(parity decision DAG)的下界。虽然决策DAG(对应resolution)和异或决策树(对应树形${\rm Res}(\oplus)$)都有已知的下界,但是异或决策DAG的下界目前还没有人会证。可惜的是,本文的技术只能用来证异或决策树的下界,而不是异或决策DAG的下界。

The Strength of Equality Oracles in Communication

众所周知,判断两个串是否相等(${\rm EQ}$)需要$\Omega(n)$的确定性通信复杂度,但是只需要$O(\log n)$的随机通信复杂度。${\rm EQ}$和随机通信复杂度并不等价——有一些其他的通信问题,虽然随机复杂度也是$O(\log n)$,但是带${\rm EQ}$ oracle的确定性通信复杂度仍然是$\Omega(n)$的。这篇文章研究的是:在别的模型(例如非确定通信、Arthur-Merlin通信)下,${\rm EQ}$ oracle的作用有多大?有趣的是,站在矩阵的角度思考的话,这个问题对应的是blocky rank的变种。

一个矩阵是blocky的,当且仅当它能够由某个单位矩阵从如下变换得来:(1)复制某一行或某一列;(2)删除某一行或某一列;(3)将行和列重排。如下图是一些blocky矩阵的例子:

令$M$为一个0/1矩阵,我们记其blocky覆盖数为$C_1^B(M)$,记其blocky划分数为$\chi_1^B(M)$。这两个数的定义如下:

  • 我们需要至少$C_1^B(M)$个blocky矩阵才能覆盖$M$的所有$1$。(也就是$M$等于这些blocky矩阵的按位或 / entry-wise OR。)
  • 我们需要至少$\chi_1^B(M)$个blocky矩阵才能不重不漏地覆盖$M$的所有$1$。(也就是$M$等于这些blocky矩阵在$\mathbb{Z}$上的和。)

本文证明了上述两个度量能够刻画${\sf NP}^{{\rm EQ}, {\sf cc}}$(带${\rm EQ}$ oracle的非确定性通信复杂度)和${\sf UP}^{{\rm EQ}, {\sf cc}}$(带${\rm EQ}$ oracle的unambiguous通信复杂度)。特别地,对一个通信问题$f$,如果令$M_f$表示它的矩阵,那么:

\begin{align*}
{\sf NP}^{{\rm EQ}, {\sf cc}}(f) =&\,\log C_1^B(M_f) \le O\left({\sf NP}^{{\rm EQ}, {\sf cc}}(f)\cdot \log n\right),\\
{\sf UP}^{{\rm EQ}, {\sf cc}}(f) \le&\,\log \chi_1^B(M_f) \le O\left({\sf UP}^{{\rm EQ}, {\sf cc}}(f)\cdot \log n\right).
\end{align*}

本文同时也证明了一些${\rm EQ}$ oracle表现得很奇怪的地方:

  • 对于${\sf NP}^{\sf cc}$和${\sf UP}^{\sf cc}$通信来说,调用一次${\rm EQ}$和调用很多次${\rm EQ}$是等价的,也就是:${\sf UP}^{{\rm EQ}, {\sf cc}} = {\sf U}\cdot {\rm EQ}^{\sf cc}$以及${\sf NP}^{{\rm EQ}, {\sf cc}} = \exists \cdot {\rm EQ}^{\sf cc}$。但是对于${\sf P}^{\sf cc}$通信来说就不等价了——事实上对任意$k$,存在能用$k$次${\sf EQ}$ oracle但是不能用$k-1$次${\sf EQ}$ oracle的通信问题。
  • 在没有${\sf EQ}$ oracle的时候,我们知道${\sf P}^{\sf cc} = {\sf UP}^{\sf cc}$。但是在有${\sf EQ}$ oracle的时候这件事情就不对了:${\sf P}^{{\rm EQ}, {\sf cc}} \ne {\sf UP}^{{\rm EQ}, {\sf cc}}$。

本文还研究了所谓的${\rm Sink}\circ {\sf XOR}_2$函数。这个函数是用来推翻log-approx-rank猜想的反例,它的随机通信复杂度是$\Omega(\sqrt{n})$,但是approx rank只有$O(n^2)$,所以${\sf R}^{\sf cc}({\rm Sink}\circ {\sf XOR}_2)$随着$\log \widetilde{\rm rk}({\rm Sink}\circ {\sf XOR}_2)$是指数级增长的。这个函数的定义如下:

  • ${\rm Sink}$的输入是一张$n'$个点的竞赛图——也就是一张完全图,但是每条边都有个定向。(所以输入长度是$n = \binom{n'}{2}$。)输出等于$1$当且仅当图中有一个汇点(也就是出度为$0$的点)。
  • 然后我们把这个函数套上${\sf XOR}_2$。假设Alice手中有一个长度为$n$的串$A$,Bob手中有一个长度为$n$的串$B$。如果$A_{(u, v)} \oplus B_{(u, v)} = 1$,那么我们让这张图中$u$连向$v$,否则让这张图中$v$连向$u$。Alice和Bob的任务是求出图中有没有汇点。

很容易看出这个函数的${\sf U}\cdot {\rm EQ}^{\sf cc}$复杂度顶多是$O(\log n)$。我们只需要猜一个汇点$v$,然后Alice和Bob对$v$的邻边调用一次${\sf EQ}$ oracle来判断$v$是不是汇点即可。因为CMS18证明了${\rm Sink}\circ {\sf XOR}_2$的${\sf coMA}^{\sf cc}$复杂度是$\Omega(n^{1/4})$,所以这篇文章也给出了${\sf U}\cdot {\rm EQ}^{\sf cc}$和${\sf coMA}^{\sf cc}$的分隔。

最后提一些open problem。视频中提到了如下问题:${\sf P}^{{\rm EQ}, {\sf cc}} = {\sf NP}^{{\rm EQ}, {\sf cc}} \cap {\sf coNP}^{{\rm EQ}, {\sf cc}}$吗?${\sf P}^{{\rm EQ}, {\sf cc}} = {\sf UP}^{{\rm EQ}, {\sf cc}} \cap {\sf coUP}^{{\rm EQ}, {\sf cc}}$吗?以及我很感兴趣的问题是:可以证明无条件的$C_1^B$和$\chi_1^B$的下界吗?因为blocky rank对应的是${\sf Sum}\circ{\sf THR}$的电路复杂度下界,$C_1^B$和$\chi_1^B$看上去比blocky rank弱一点点(但不多),所以这两个度量的下界可以看成是证明${\sf Sum}\circ {\sf THR}$下界的进展?

 


登录 *


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