ITCS 2023 游记

去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}$。

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}$复杂度下界（BFT98, San09），不同之处在于我们只需要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问题（Korten21, RSW22）的“黑盒”形式：给出一个函数$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$的遛狗距离。

为了定义“翻转遛狗距离”，我们先写出遛狗距离的表达式。假设人和狗都在某个度量空间$\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)}$时间。