2023 年度总结

既然是2023年的总结，就从2023年1月1日写起吧。作为新年仪式，我把好朋友叫到屋子里来煮了一餐咖喱乌冬。那是我第一次把朋友叫到家里一起做饭，当时我的做饭水平还非常差劲（现在也没好到哪儿去），而且还买错了乌冬面。我们一边做饭一边外放各自的树立口歌单。说起来，在牛津能遇到现实中能一起听《.》和《.》的朋友，是一件很幸运的事情呢。

作为邪教徒，我们会把盛好的咖喱乌冬面放在我们的邪教图腾面前膜拜——

ん↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑

没过几天我就离开牛津去了ITCS。（特别鸣谢DIMACS的金主爸爸们的支持呜呜呜）熟悉我的人可能知道我2022有一堆会议没去成心里十分不爽——而这次ITCS之旅也意味着我四处奔波疯狂开会的2023开始辣！

ITCS之后是为期四个月的Simons Meta-complexity program，于是我在伯克利住了四个月。伯克利的天真蓝，阳光真明媚，但是哪天天气不够好的时候我就无法喜欢上这座城市了。Simons到处都是大白板和五彩沙发，还有一台大大的咖啡机，正如其宣传所说是“为科研合作专门设计”的。如果我以后住的地方也有这么多大白板和五彩沙发以及大大的咖啡机，我还能时不时host一些同行来大白板面前讨论学术的话，我做梦都会笑醒吧。

依稀记得情人节（2月14）那天cls跟我吐槽说最近没有什么科研灵感，想拿CT21b做点什么却没有想法。于是那天晚上我把cls喊了出来，瞎bb了一个CT21b可能可以拿来搞伪确定性算法（OS17）的proposal，我当时猜测可以做到准多项式（quasi-polynomial）时间。cls听了非常激动而且觉得这个proposal“肯定是对的”，第二天就把我和Igor叫出来又讨论了一晚上，并且拿出了他的专业知识（SU05，当时我们几个人当中只有他懂）把这些东西改进到了真正的多项式时间。

后来我们把这些东西写成了一篇文章。我们一边写一边去成都style吃饭，Igor还带我们一起吃冰淇淋一起聊天。coauthor生活得很近的话，每天写完文章一起吃饭，就会像战友一样。Part of this work was done in Chengdu Style.

再后来cls和我都不是情人节晚上有时间约出来聊学术的人了O(∩_∩)O。不过这都是后话了。

现在回顾起来我在Simons的状态并不算很好，比如说整个三月都在下雨搞得我整个三月心情都很不好，甚至写文章的时候也没出什么力，SU05也是赶鸭子上架学的（土下座）。（也有可能是准备了两个talk搞得有点心力交瘁，笑。）后来四月天气晴朗得多了，FOCS ddl也结束了，我的状态也就变好了一些。Simons有很多活动，搞到后面很容易精疲力尽，比如说cls就经常抱怨精疲力尽（我倒是会故意回避一部分活动）。不过也真的能学到很多东西，我本人别的不说至少算是入门了proof complexity和bounded arithmetic。

我在Simons积累了一些好习惯，比如说隔几天跑一次步、每天在Keep上练腹肌。不过回到牛津就坚持不下去了，现在腹肌也一夜回到解放前了。说起来，锻炼之类的事情还是只有在稳定的环境里才能坚持下去。我下半年住的房子很小（没地方放瑜伽垫），之后又各种旅游（每周都要换个地方），所以没法坚持锻炼。

此外，太累了需要放松的时候会偷偷调一些无他五（笑）。无他五比树立口好用一万倍！引擎免费不说，如果声库质量高的话，产生的声音也比树立口要优质一些。就是对“日语windows”除外的环境支持不太好。

四月UCB的樱花开了！每走到那里我都忍不住会拍几张樱花照。

今年搞的另一个结果是$\mathsf{S}_2\mathsf{E}$的电路复杂度下界。因为我们（CLORS）搞的iterative win-win似乎很适合做伪确定性算法，而电路复杂度下界说白了就是Range Avoidance的伪确定性算法，所以应该试着拿iterative win-win做做电路复杂度下界。Iterative win-win还需要一个hardness-randomness tradeoff，比如说CLORS就是拿CT21b做的这个hardness-randomness tradeoff。于是，我们拿Korten21做这个tradeoff就好了。经过了一些试错之后，我们用这个思路搞出了$\Sigma_2\mathsf{E}\not\subseteq\mathsf{SIZE}[2^n/n]$，经过$\mathsf{S}_2\mathsf{P}$专家Shuichi点拨了一下之后，我们把结果改进到了$\mathsf{S}_2\mathsf{E}/_1\not\subseteq\mathsf{SIZE}[2^n/n]$。我记得$\Sigma_2\mathsf{E}$的复杂度下界搞出来之后我特别特别高兴——毕竟也算得上是40年的open problem吧（笑）。好久好久都没有这么高兴过了，可能这辈子都不会有下一次了。

不过，在我们把文章放到arXiv和ECCC后没过多久，Zeyong Li就发现我们想复杂了，并且给了一个简单直接的能够证明$\mathsf{S}_2\mathsf{E}\not\subseteq \mathrm{i.o.}\textrm{-}\mathsf{SIZE}[2^n/n]$的证法！说实话我们看到这个证明之后惊呆了，我们也没有想过“win-win其实是根本不需要的”！我一直觉得前人没有理解清楚（Kannan类型的）电路复杂度的本质，直到Korten等人仔细研究了Range Avoidance并把它和bounded arithmetic里面对dwPHP的研究联系到一起时，我们对“电路复杂度”的理解才算得上摸着了边。事实上不仅仅是前人没有理解清楚这个问题，我们也没有理解清楚它，以至于“一定要win-win才能证出$\Sigma_2\mathsf{E}$的下界”这个思维定式深深地刻在了每一个人的脑海中。后来cls一直跟我说“complexity theory走了四十年的弯路”。

我在日记里夸下海口：“我相信这套技术会对复杂度理论里的win-win analysis产生颠覆性的影响”。要是事情真的有这么简单就好了！我们仍然不会证$\mathsf{MAEXP}/_1\not\subseteq\mathsf{SIZE}[2^{\varepsilon n}]$，我们还是有大量的win-win arguments不知道怎么做到更优。Iterative win-win目前能做到的只有CLORS和CHR这两个例子而已，CHR的win-win还不是必须的。到底什么时候能做iterative win-win？Iterative win-win似乎是需要所谓“hardness-randomness tradeoff”才能做的，CT21b (NW + GKR)和Korten21都可以理解为“hardness-randomness tradeoff”，但是到底什么才是“hardness-randomness tradeoff”？我不知道。

或许以后会有颠覆性的影响吧，或许哪天人们就能理解清楚什么是iterative win-win了吧。只是远远地看到了冰山浮出水面的样子，什么时候才能测绘出冰山的全貌呢。前人们做出了一个个breakthrough，他们对他们自己做出的东西的理解也不算很透彻，他们只是做出了成果，但是理解这些成果需要后人几十年的努力。或许他们也这么叹息过吧。

我在离开Simons之前心血来潮沿着附近的几条路暴走了一波。比如说我家住在Spruce St的南端，于是我一路走到了Spruce St的最北端。大概去程和回程分别走了一个多小时吧。因为事先并没有看Spruce St有多长，所以去程心里没有什么数，而且有好几次觉得自己可能走不到最北端了所以打算放弃。还好最后坚持下来了！看到Spruce St的尽头的时候，虽然并没有什么特别的风景，但是心里又开心又感动，像是完成了什么很了不起的成就一样。幸亏我在牛津的时候没有尝试走完Banbury Rd

这张图就是Spruce St最北边的风景！

我也去了Euclid Rd的最北端！今天写这个博客的时候，在地图上翻，发现这两条路的最北端竟然如此接近（不到500米吧）。早知道我应该只走一次，从Spruce去，从Euclid回的。后来把这些照片发给一个骑自行车的朋友，她说这块地方她们经常骑hhhhh

以及我还去了伯克利山上的Big C。那座山不是很好爬，比较陡峭（起码有45°）。山顶上似乎有一些科研机构，我没进去，总之爬到Big C就溜了。我觉得Big C一点也不好看（。。。。。）和我累死累活爬山流下的大把汗水相比，Big C的颜值令人大跌眼镜（。。。。。。。。。）

5月回到了牛津！然后就和美少女ccm面基了（大概8-9年没见了吧，哭哭）。不过面基次数变多似乎是6月的事情。6.10晚上欧冠决赛那天我把她拉到酒吧去看，我记得曼城夺冠的那一刻我们俩紧紧相拥——虽然我们俩没有一个是曼城球迷。那几天我们还一起做了两顿饭，我家一顿，她家一顿。美少女做可乐鸡翅就是好吃些！（ccm我知道你在看，不知道你还记不记得你的可乐鸡翅hhhh）

再后来我们就在一起了。

7月的时候我们去利物浦度蜜月（这个词是这么用的吗）！ccm把我拉入了攀岩的坑。据说我“第一次爬就爬了v2”，“很厉害”。不过我只记得我们互相拍了不少的爬墙视频。有一些很难的线路，ccm失败了好几次之后终于成功了，当时我们俩都很激动。后来11-12月我再去攀岩的时候，我在尝试之前失败了的线路时，在失败了的那个点会产生一些心理作用（？），不敢继续尝试了。我大概还没有培养出一个攀岩者应该具有的不畏挑战、勇往直前的心态吧。

对利物浦剩下的记忆可能就是海风了！我们会在海边手牵手走路，然后聊几个小时的天。两个人的头发都被吹得很乱，像两个幸福的疯子。

回到了牛津之后，我们变本加厉（？）地一起做饭吃。我们会一起计划食谱，一起去超市买食材，顺便搞点两人都喜欢的果汁喝。做饭时出力比较少的人（一般是我）会负责洗碗。吃完饭后当然要一起散步。照道理ccm应该没我有经验的样子（毕竟出国时间更短），但是她似乎比我懂很多门道的样子，比如说怎么拿奶酪做白人饭，还有怎么拿黄油代替菜籽油炒饭等等。说句实话，那段时间我感受到了我想要的生活，平淡但是温暖的那种。

此外我还入坑了baba is you。这游戏太天才了！不玩的人人生绝对失败，pull/shift/swap/word都能造出可以细细品味的关卡。我是在手机上买的，有段时间每天饭点都要玩，一边玩一边下饭，睡前也要玩，玩累了就能入睡。ccm的情敌属于是。年末又在steam上购入了带关卡编辑器的版本，关卡编辑器更好玩了！每天都可以摸摸keke小脑袋（keke is pet）然后金光闪闪地搞钱（ca$h is best）。我造了几个关卡但是因为网络似乎有点问题所以还没发出来（敬请期待）。

我2023下半年的安排非常混乱。8月初去IC搞了点proof complexity，但是可惜想搞的东西失败了，目前还没有看得见的成果出来。8月底去办了美签。因为一些原因没有续学院的房子，而是9-10月住在了summertown北边一个比较便宜的小屋里面。11月去美国和（也在美国访问的）ccm再次团聚，12月在华威找Igor玩，12月16回国。

美签给人的压力很大。光是把那套流程走一遍，然后默念着因为自己做的是“计算机”所以自己在签证上是有原罪的，就已经是一件非常恶心的事情了。从结果上来说他们只check了我两周，所以似乎也没有那么坏。但是——我是个必须依赖自己是“搞TCS的”身份认同才能活下去的人。想着因为坚持自己“搞TCS的”身份认同而不得不遭受一些莫须有的东西，被一些身居高位的腐朽的眼珠儿上下打量，就觉得是令人作呕的事情。将这世界运行规律的美丽外壳剥开之后，里面的内核是如此恐怖，我想我根本还没有做好准备去面对那些东西。我还不理解怎么会有人“在看透了生活的真相之后，仍然热爱它”，或许我还不够成熟吧。

在IC的时候Iddo对我很好，我们讨论了很多proof complexity的东西。也正是在快要离开IC的时候我试着看了一些硬核的proof complexity文章，发现自己居然是有能力理解其中的一些中心思想的。以前我对捷克搞proof complexity和bounded arithmetic的人的印象就是“似乎在搞很重要的东西，但是写的文章我完全看不懂”。8月的时候突然能看懂Jan Krajicek的一些文章了，感觉他的写作其实比我想象中友好很多，而且很多文章背后有好玩的insight。（但是Emil Jerabek早期的一些文章是真的难啃，dwPHP、APC1、APC2我都需要全神贯注投入以周为单位的时间才能理解清楚在讲什么。。。。）

我在summertown的房子住了两个多月。室友是一些国内来访学的老师（还带了小孩），所以辈分上都比我大一些！但是对我非常非常好（嘤嘤嘤）。我到现在都还是怀念那里的氛围，大家时不时就会组织一些聚餐，包饺子、下火锅、或者烤肉吃。偶尔会有别的老师来参加，大家都随和又融洽。但是那间房子是真的不太行，网络不好虫子还多（。。。）不管怎么说，那段时间过得还是挺舒服的，每天在玛莎买食材（玛莎的东西比tesco和sainsbury要好吃很多）然后回家自己做，似乎把自己养胖了的样子。玛莎还可以买到好吃的水果和甜品，赞一个。

此外还经过ccm的推荐入坑了逆转裁判泥砖菜盘123，8-10月的时候每周周末都会玩！搞了一星期学术，周末就会有全新的逆转章节等着我。真宵宝宝好可爱，御剑宝宝好可爱，小冥姐姐好可爱，王都楼滚出娱乐圈，人物形象不太丰满的反倒是主角成步堂龙一（。）和幕后黑手绫里千寻（。。。。）11月在ccm眼皮子底下把3-5也打完了，那种每周都能盼望着打开一个新章节的感觉也成为过去式了。用steam上的评论说就是，很想失忆了之后再打一遍（哭哭）。在我发布这篇博客的时候逆转456精选集也出了，我还没买，总之很期待。

今年9-10月的时候，我觉得我应该脱产两个月学点bounded arithmetic。当时的想法是：比起在STOC和FOCS上发文章，学一些自己不熟悉的东西并跳出舒适圈显然是更有意义的事情。我这两个月的日常基本上就是——每天起床做早餐吃，然后骑车去pret看两个小时的bounded arithmetic。（我太喜欢pret的30镑一个月咖啡随便拿的政策了！跟我这种喝咖啡只为提神不求口感的学术打工仔简直是绝配！）中午去市中心搞点吃的，下午继续找个位置看paper。两个月后我算是入门了bounded arithmetic，至少知道啥是$\mathsf{S}^1_2(\alpha)$、啥是$\mathsf{T}^1_2(\alpha)$、能在$\mathsf{T}^1_2$中证明$\mathsf{PLS}$的totality了。不过也还有很多仍然需要学习的地方，比如说我还没学那些二阶逻辑（$\mathsf{U}^1_2$、$\mathsf{V}^1_2$），也不了解KPT witnessing。。。

我现在觉得把常见的数学证明在bounded arithmetic的子系统里面形式化是一个非常非常有意义的事情。尤其是所谓的bounded reverse mathematics——给每个定理找一个最弱的可以形式化证明它的子系统。假设有一个$\forall\Sigma_1^b$语句，也就是形如“对任意$x$，存在$y$使得blabla成立”的语句。如果这个语句真的是对的，那么它就定义了一个$\mathsf{TFNP}$问题：给出$x$，求一个合法的$y$使得前述“blabla”成立。一个很基础的事实是：前述的$\forall\Sigma_1^b$语句的证明复杂度等价于这个$\mathsf{TFNP}$问题的计算复杂度。比如，如果这个语句的证明中用了$\Sigma_1^b$语句的数学归纳（$\mathsf{IND}$），那么对应的$\mathsf{TFNP}$问题就在$\mathsf{PLS}$中。而很多常见的$\forall\Sigma_1^b$语句有着非常不简单的证明，我们可以从这些证明中挖出很多非平凡的$\mathsf{TFNP}$的子类。我最喜欢的例子是如下两个：

• （算术基本定理）对任意整数$n$，存在一串质数$p_1 \dots p_k$使得$n = \prod_{i=1}^k p_i$。（“$p$是质数”可以定义为$\forall 1<q<p, \lnot(q\mid p)$；但是这样定义只能得到一个$\forall\Sigma_2^b$语句。如果想要一个$\forall\Sigma_1^b$语句的话可以使用Pratt或者AKS，不过那样的话证明复杂度又要提升一个台阶了。。。）
• （Razborov-Smolensky）任意大小为$2^{n^{1/2d}}$的$\mathsf{AC}^0[2]$电路无法计算$\mathsf{MAJ}$函数。（对应的$\mathsf{TFNP}$问题是一个“refuter”问题：给出一个大小只有$2^{n^{1/2d}}$的$\mathsf{AC}^0[2]$电路$C$，求一个满足$C(x)\ne \mathsf{MAJ}(x)$的输入$x$。我认为这个问题的复杂度是个非常有意思的open problem。）

10月27日的凌晨我拖着大行李箱赶往希斯罗机场，随后开启了我为期10周的颠沛流离（？）之旅。（草，以后还是想住得安稳些，别他妈隔一周搬一次家了。。）前三周去了美帝，见了见cls然后开了点会主要是在和ccm美少女一起干饭一起玩。因为辗转各地而且自习环境也不是很好，所以并没有认真搞什么科研。在IAS和Robert Andrews讨论了一些代数复杂度的东西，（再一次）勾起了我想入门代数复杂度的中二之魂，但是很可惜这两个月一直没有时间深入研究。说起来IAS的风景真是绝美啊，人生最大的乐趣莫过于在这样的蓝天绿树青草的陪伴下每天与数学为伍了。

从美帝回来之后就在华威访问Igor。我非常幸运地住进了Maths House！Maths House是真正的大豪斯，有客厅、若干卧室、厨房，卧室里还有大大的黑板（和维基百科上的图片一模一样），数学家看了直接馋哭了。

刚到华威的时候因为要倒时差所以经常通宵，于是我得到了23:00-8:00连续九个小时啃paper不被任何人打扰的宝贵机会。我买了咖啡和食材，凌晨三四点的时候做饭吃。虽然我不是熬夜党但是我竟莫名其妙地很喜欢这样的作息，感觉像是每天有八九个小时完完整整的自由。不做饭的时候就对着黑板啃APC1和APC2那两篇文章，看完之后对“随机算法”这种东西的理解也会加深呢。

此外我在Maths House提升了烹饪技能，学会了做咖喱（选了一张好看的，但是实际上油放多了所以并不是很好吃）：

最后几周回到了国内，在各大高校宣讲我的$\mathsf{S}_2\mathsf{E}$的复杂度下界骗吃骗喝。在北大程宽老师的熏陶下我又对${\sf BPL}$ vs ${\sf L}$和extractor感兴趣了（笑）。感觉最近在${\sf BPL}$ vs ${\sf L}$有很多新的进展，所以我似乎有必要花点时间学一下。cls也对${\sf BPL}$ vs ${\sf L}$非常感兴趣来着，他觉得跟${\sf BPP}$ vs ${\sf P}$不同，人们在${\sf BPL}$ vs ${\sf L}$上是真的取得了不错的进展的（例如${\sf BPL} \subseteq {\sf L}^{3/2}$），所以从这方面来讲${\sf BPL}$ vs ${\sf L}$可能会更“可做”一点？另一方面，现在对去随机化的研究集中在两个方面——更快地去随机化（例如DMOZ20和CT21a——${\sf BPTIME}[T] \subseteq {\sf DTIME}[T\cdot n^{1+o(1)}]$）和用更弱的假设搞去随机化（例如CT21b、LP22、LP23）。这些热点在对${\sf BPL}$的去随机化上也有不少研究，例如现在已经有了一些${\sf BPSPACE}[S] \subseteq {\sf DSPACE}[(2+o(1))S]$甚至$(1+o(1))S$的证据。我们之前需要一些很强的电路复杂度下界（${\sf DSPACE}[n]\not\subseteq {\sf SIZE}[2^{\varepsilon n}]$）才能推出${\sf BPL} = {\sf L}$，这个事情显然是不优的（因为${\sf BPL} = {\sf L}$应该比${\sf BPP} = {\sf P}$要“容易”很多，不应该需要更强的复杂度下界）；现在也有论文试图减弱所需的复杂度假设。

说到extractor，我感觉我们做复杂度理论和去随机化的人不能一提到extractor就只知道Nisan-Wigderson和Direct Product。（很可惜我本人就是这种人。。。）所以我应该多学点更先进的extractor构造方式。NW和DP在meta-complexity中已经掀起了一股腥风血雨，所以说不定那些更好的extractor能掀起另一波腥风血雨。此外，有一些和extractor相关的其他物件（近亲例如disperser、condenser、merger，远亲例如two-source extractor、non-malleable extractor），不知道会不会在复杂度理论里派上用场。我觉得把extractor的证明写成reconstructive的形式（也就是如果有adversary $A$能够区分extractor的输出和真随机，那么就有一个adversary $B$能够“证明”输入的随机源不是$k$-source，并且$B$的复杂度跟$A$差不多）对复杂度理论而言是非常有意义的事情。害，也不知道这么多坑什么时候能够填完了。

虽然这两个多月没有扎扎实实做什么科研，但是我花了一些时间思考一些更宏大的议题。我是个什么样的人？以后想从事什么样的工作、过上什么样的生活？我觉得我大概已经无法离开TCS了，也无法想象自己去做TCS和数学之外的工作。我在这方面有着执拗、偏激的自我认同，我希望周围所有人都可以把我当成理论计算机科学家（或者“数学家”），如果我感受到了不被当成“理论工作者”看待的目光的话会感到痛苦。我似乎更喜欢稳定的、带有确定性的生活的样子，每天的生活流程固定，花尽可能多的时间在科研上，如果周末有一些科研之外自由支配的时间就更好了。但是在科研的内容方面我又不喜欢这种稳定性，我希望每隔一段时间就能试着跳出舒适圈去学习自己不熟悉的东西。对我而言理想的工作环境应该能给我足够的自由度去探索、学习，而不是被发表文章和晋升的压力所支配。