CCC 2020 游记

如果说今年爆发的Trump virus给我带来了任何好处的话，那就是我免费蹭了一次CCC。。。

会议开幕的时候，主持人对我们说：“（假设）你们现在就坐在中间这幢大楼的会议厅内。。。”（呜呜呜，想出去玩了

以下是一些我觉得有意思的paper。可以在youtube上看到对应的talk。我主要选择的是和我自己的research interest有关的paper。（其实并不是。没有选多少quantum和algebraic complexity的paper只是因为我看不懂（

Hitting Sets Give Two-Sided Derandomization of Small Space

只看了视频，我的理解是这样的。首先，假设我们有一个ROBP，我们希望估算出它的accept probability。我们构造一个随机算法，然后证明如果这个算法使用的随机串是“locally consistent”的，那么我们估算的accept probability是准确的。于是，我们只需要使用hitting set来找出一个locally consistent的随机串即可。我们可以构造一个更大的ROBP，使得它接受的串都是locally consistent的，而且它接受大部分的随机串，于是hitting set确实可以用来找出locally consistent的随机串。最后，locally consistency是可以在logspace内验证的，于是我们可以在logspace内估算出ROBP的accept probability。

emmm感觉视频讲得比我在这里瞎扯要清楚多了啊。。。。

Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions

也是只看了视频，没看paper，感觉是一篇非常强的hardness magnification文章。

文章中定义了一个叫“${\sf E}$ vs ${\sf SIZE}(2^{o(n)})$问题”的问题，不严谨的定义如下：给出一个函数$f$（的truth table），当$f\in{\sf E}_{/O(n)}$的时候输出“Yes”，当$f\not\in{\sf SIZE}(2^{o(n)})$的时候输出“No”。注意到，如果我们相信电路复杂度下界，比如说${\sf E}\not\subseteq{\sf SIZE}(2^{o(n)})$成立的话，那么没有任何算法能够解决这个问题。（因为给出一个在${\sf E}$中，但是不在${\sf SIZE}(2^{o(n)})$中的函数$f$，你既得输出“Yes”又得输出“No”。）然而，如果我们能够证明$\underline{N^{1+o(1)}}$大小的$\underline{{\sf AC}^0\circ{\sf XOR}}$电路无法解决这个问题，那么我们就能够得到非常强的${\sf AC}^0\circ {\sf XOR}$的PRG，并且证明${\sf EXP}\not\subseteq{\sf NC}^1$！

值得一提的是，这篇文章的结果是non black-box的。hardness magnification的目的是：证明如果一个问题$L$有$N^{1+o(1)}$大小的电路复杂度下界，那么另一个问题$L'$不能被多项式大小的电路计算；于是，“如果$L\not\in{\sf SIZE}(N^{1+o(1)})$，那么${\sf EXP}\not\subseteq{\sf P}_{/{\rm poly}}$”。之前的hardness magnification的做法都是给出$L'$的多项式大小的电路，我们把该电路当成一个黑盒子，并用其构造出$L$的非常小的电路。（比如说，如果$L$的长度为$N$的输入可以在线性时间内规约为$L'$的长度为$\ell=N^{o(1)}$的输入，那么$L'$的多项式大小的电路就会变成$L$的$N+{\rm poly}(\ell)\le N^{1+o(1)}$大小的电路。）相反，这篇文章并不是把$L'$的电路当成黑盒子用，而是真实地用到了“$L'$的电路很小”这个性质。

Algebraic Hardness versus Randomness in Low Characteristic

这篇文章关心的是代数复杂度下界能否用来做去随机化（derandomization），具体地说就是用确定性算法判定一个多项式是不是零（polynomial identity testing）。Kabanets-Impagliazzo证明了一些结果，但是在考虑的域的characteristic比较小的时候（比如说${\rm GF}(2^n)$）他们的结果好像不是很令人满意？于是就有了这篇文章。

我不是很懂这方面的东西。。。我只知道视频中把这个问题最终归结为求一个多项式的$p$次方根，其中$p$是characteristic。文章中给出了一个开$p$次方根的算法：给出一个计算$f^p$的、大小为$s$的（代数）电路，我们可以构造一个大小不超过$s\cdot p^{O(n)}$的电路来计算$f$，其中$n$是$f$的变量个数。这篇文章中$p$很小且$n$是常数，所以可以认为这个开根算法很高效。视频里讲了$n=1$且$p=2$的情况，讲得很清晰。

另外，今年CCC还有一篇文章（“Factorization of Polynomials Given by Arithmetic Branching Programs”）也和这个相关。这篇文章讲的是给出一个多项式$p$，如果$p$能被大小为$s$的arithmetic branching program（ABP）计算，那么$p$的任何因子能被大小为${\rm poly}(s)$的ABP计算。

Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas

best student paper，太神了。

这篇文章研究的问题是：给出一个${\sf MCSP}$-oracle（只返回“Yes”或“No”的那种），我们能否在多项式时间内给出一个函数的truth table，找到计算这个函数的最小的电路（search-${\sf MCSP}$）？如果${\sf MCSP}$是${\sf NP}$-完全的，那么这个问题显然是可行的。然而目前没有任何非平凡的做法。

对于${\sf MFSP}$（最小化formula而不是最小化circuit）的情况，这篇文章给出了非平凡的做法！事实上，这个做法的时间复杂度是${\rm poly}(N, t)$，其中$N$是truth table的长度，$t$是这个函数的“几乎最小的formula”的个数。

我感觉这篇文章最重要的技术是一个“heuristic test”，给出函数$f$和$g$的truth table（以及${\sf MFSP}$-oracle），测试$g$是不是$f$的最优formula分解中的一部分。（也就是说，把$f$的最优formula的最顶层的gate拆掉之后，能够得到$g$和另一个函数$h$。）说它是“heuristic”是因为，如果$g$不是$f$的最优formula分解中的一部分，$g$还是有可能通过这个test，因此我们需要想办法让这个heuristic test通过尽量少的$g$（但是仍要通过所有合法的$g$）。

另外，这个技术好像在circuit的情况下用不了啊。。。

Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction

一篇fine-grained parameterized complexity的文章。考虑的问题是：给出一个布尔CSP问题，要求出一个恰好包含$k$个$1$的答案，它的复杂度是多少？

布尔CSP问题大致是这样的：有$n$个$0/1$变量以及一些“限制”（constraints），每个限制只和常数个变量有关，要求给这些变量赋值使得每个限制都是对的。比如说在$3\text{-}{\sf SAT}$中，每个clause都是一个只和$3$个变量有关的限制（例如$x_i\lor \bar{x}_j\lor \bar{x}_k = 1$）；在Vertex-Cover中，每条边都是一个只和$2$个变量有关的限制（某两个点中必须有一个$1$）。

文章考虑的是求出恰好包含$k$个$1$的满足所有限制的赋值。对于$3\text{-}{\sf SAT}$，这个问题只能用暴力算法在$n^{(1-o(1))k}$时间内解决（假设“$3$-uniform Hyperclique assumption”是对的）；而对于Vertex-Cover，这个问题有${\sf FPT}$算法（$2^{O(k)}+O(kn)$），可见这两个问题的复杂度完全不一样。

文章把所有的布尔CSP分成了四类，并且精确地刻画了每一类布尔CSP的复杂度。（当然，需要若干assumptions。）这篇文章的亮点是用“Schur bound”给第三类CSP设计了一个$f(k)n^{O(\sqrt{k})}$复杂度的算法。我没太看懂具体的算法。。。不过我可以说一下Schur bound是什么：给出面值为$d_1,d_2,\dots,d_\ell$的硬币，其中$2\le d_1<d_2<\dots<d_\ell$，且$\gcd(d_1,d_2,\dots,d_\ell)=1$。Schur bound说的是对任意$x\ge (d_1-1)(d_\ell-1)$，我们可以用这些硬币凑出面值$x$。

NP-Hardness of Circuit Minimization for Multi-Output Functions

这篇文章证明了${\sf MCSP}$的一些变种是${\sf NP}$-完全的。其中两个“看上去已经非常像${\sf MCSP}$，但是可以证出是${\sf NP}$-完全”的问题是：

• ${\sf Partial}\text{-}{\sf MCSP}$：给出一些输入$x_i$和它们对应的输出$f(x_i)$，是否存在大小不超过$s$的电路和这些输入输出相对应？（“机器学习”问题）
• ${\sf Multi}\text{-}{\sf MCSP}$：给出一个有很多输出的函数$f:\{0,1\}^n\to\{0,1\}^m$，这个函数是否存在大小为$s$的电路？

在${\sf Multi}\text{-}{\sf MCSP}$的复杂性证明中，作者构造的函数有非常多的输出（$m$是$n$的指数级别）。会议中作者提出了这样的问题：在这个规约中$m$最小能达到多少？（$m=1$的话就是${\sf MCSP}$了。）

PS：我个人认为${\sf MCSP}$这个问题本身有一些很奇妙的结构，使得它跟它的那些变种都不一样，并且因此它的${\sf NP}$-完全性会非常难证（如果它确实是${\sf NP}$-完全的话）。我当然说不清奇妙的结构是什么（否则我就能发paper了，笑）。

Circuit Lower Bounds from NP-Hardness of MCSP under Turing Reductions

这篇文章讲的是，如果${\sf SAT}$可以图灵规约到${\sf MCSP}$，并且这个规约比较“中规中矩”的话，我们可以用这个规约来证明电路复杂度下界（${\sf EXP}\not\subseteq{\sf P}_{/{\rm poly}}$）。

这篇文章的技术比较有意思：作者先用一些简单的方法回答所有${\sf MCSP}$询问（比如说无脑回答yes），得到一个比较快的计算${\sf SAT}$的程序。如果这个程序在计算${\sf SAT}$时出错了，那么他们用Gutfreund、Shaltiel和Ta-Shma的方法找到一个使这个程序出错的${\sf SAT}$输入。在这个输入上，“无脑回答${\sf MCSP}$询问”会出问题，从而这些询问中输入的truth table有电路复杂性下界。由于GSTS需要用到算法的源代码（而不是把算法当成一个黑盒子），所以这篇文章的技术是non black-box的。或许这个技术比以前的black-box技术更有潜力解决一些其他问题？

Multiparty Karchmer-Wigderson Games and Threshold Circuits

（单调的）Karchmer-Wigderson游戏是通信复杂度中一个很著名的问题：给出单调函数$f$，Alice手上有$x$，Bob手上有$y$，且满足$f(x)=1$，$f(y)=0$。两人希望通信后求出一个下标$i$，使得$x_i=1$，$y_i=0$。Karchmer和Wigderson证明了该问题的通信复杂度恰好是$f$的深度，也就是计算$f$的单调电路需要的最小深度。

这篇文章把KW游戏推广到了多人。我们先仍然考虑两个人的情况，并假设$f$是$2n+1$位上的Majority（也就是$f(x)=1$当且仅当$x$中有至少$n+1$个$1$）。于是Alice手上有一个包含至少$n+1$个$1$的$x$，Bob手上有一个包含至多$n$个$1$的$y$，且两人希望找到一个$i$使得$x_i=1$，$y_i=0$。如果我们把Alice手上的串取反，那么这个问题等价于：Alice和Bob分别收到了两个包含至多$n$个$1$的串，且双方希望找到一个同时为$0$的下标。那么很显然可以这样推广到多人：有$k$个人，每个人收到一个长度为$kn+1$的串，其中至多有$n$个$1$；要求找到一个下标使得所有人的串在这个下标都是$0$。

这篇文章证明了这个游戏的通信复杂度和使用${\sf THR}^k_{k+1}$门电路计算${\sf THR}^k_{nk+1}$的最小深度是同阶的。在这里${\sf THR}^k_N$为一个$N$位函数，返回$0$当且仅当输入中$1$的比例不超过$1/k$。

同时这篇文章解决了一个非常经典的问题：能否确定性地构造一个$O(\log n)$深度的${\sf MAJ}_3$门电路来计算$2n+1$位的${\sf MAJ}$函数？Valiant给出了一个随机性的构造，（好像乱接线就行了？）Ajtai-Komlós-Szemerédi给出了一个确定性的使用${\sf AND}$和${\sf OR}$门的构造（AKS排序网络），但是把${\sf AND}$和${\sf OR}$门用${\sf MAJ}_3$门代替好像open了几十年。这篇文章给出了一个把AKS构造的电路直接变成只有${\sf MAJ}_3$门的电路的方法，作者还特意录了一段视频来讲解这个方法。（讲得非常清晰！）

Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates

个人认为这篇文章最重要的idea是它给出的定义，也就是${\sf Formula}\circ {\cal G}$这个电路类。Avishay Tal证明了计算内积（Inner product，${\sf IP}(x, y) = \bigoplus_{i=1}^n(x_i\cdot y_i)$）需要$n^{2-o(1)}$大小的bipartite formula——也就是在允许给Formula的叶子放上任意只与$x$或者只与$y$有关的函数的情况下，${\sf IP}$都需要$n^{2-o(1)}$大小的formula。在这篇文章中，作者考虑了bipartite formula的增强版：就算叶子上允许放一些通信复杂度很小的函数（bipartite formula对应着通信复杂度为$0$的情况），也可以证明$n^{2-o(1)}$的formula lower bound。这一类通信复杂度很小的函数其实很expressive，比如说已经包括了symmetric function（$\sf SYM$）和linear threshold function（$\sf THR$）。这种${\sf Formula}\circ{\cal G}$电路的一个很重要的特例是“polytope”，也就是${\sf AND}\circ {\sf THR}$；用这篇文章的方法可以构造新的针对polytope的PRG。

做法呢，还是用Avishay Tal的做法，用一个low-degree polynomial来近似上面的Formula。具体细节没太看。

作者提出了这样的问题：能否证明任何$n^{2+\epsilon}$大小的${\sf Formula}\circ{\sf XOR}$电路下界？如果不要底下的${\sf XOR}$函数的话，Andreev函数需要$n^{3-o(1)}$大小的formula；但是加了底下的${\sf XOR}$之后，Andreev函数只需要$O(n)$（？）大小就可以计算。

Junior-Senior Lunch

最后：我还参加了一些Junior-Senior lunch，得到了和大佬近距离接触的机会。（如果是线下会议的话我可能会社恐，不敢跟大佬聊天。。。况且CCC在线下举办的话我肯定是去不了的。。。从这个角度来说我还真得感谢Trump virus？）

印象比较深刻的是和Russell Impagliazzo讨论了一些algebraic complexity？有一位印度小哥提到了Kabanets-Impagliazzo的PIT算法。就算假设最强的代数复杂度下界，这个算法的复杂度也是$2^{{\rm polylog}(n)}$，不知道怎么改进到多项式复杂度。。。好像还扯到了能不能把Carmosino-Impagliazzo-Kabanets-Kolokolova（就是学习${\sf AC}^0[2]$电路的那篇论文）推广到代数复杂度。。。（说实话我没有跟上他们的flow，因为我实在不懂代数复杂度

我问了一句“有没有人研究代数复杂度的${\sf MCSP}$”。。。好像是有的，但是还没有人做出很好的结果？代数${\sf MCSP}$的定义本身就是个问题：代数复杂度计算的是多项式而不是truth table，而truth table相同的多项式可以是不一样的（比如说$x^p-x$和$0$）。如果直接给truth table的话无法capture到这一点。。。？

也不知道这个问题和“algebraic natural proof”有没有关系。。。？反正感觉是个大坑。。。