CCC 2020 游记

r_64 posted @ 2020年7月31日 18:09 in 未分类 , 246 阅读

如果说今年爆发的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”有没有关系。。。?反正感觉是个大坑。。。


登录 *


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