将赴伯克利深造，常州学子获全球计算机理论顶会 STOC 2020最佳论文奖

吴克文是北京大学信息科学技术学院图灵班 16 级本科生，高中毕业于江苏省常州高级中学。他的科研兴趣为理论计算机，如：复杂性理论、算法设计与分析、密码学等。北大表示，作为北京大学图灵班第一届毕业生，吴克文将很快前往 UC Berkeley 继续学习。

6月25日，北京大学前沿计算研究中心官方报道称，在全球计算机理论顶会 STOC 2020 上，北大本科生吴克文有两篇论文发表，其中一篇获得了最佳论文奖。

根据北京大学前沿计算研究中心官方公众号的报道，6 月 25 日，ACM 计算理论年会 STOC 2020 上传来一条好消息：北京大学信息科学技术学院 16 级图灵班学生吴克文参与的论文《Improved bounds for the sunflower lemma》荣获会议最佳论文奖。

作为计算机理论领域的全球顶级学术会议，ACM 计算理论年会（ACM Symposium on Theory of Computing，STOC）始于 1969 年，今年已经举办了 52 届。

STOC 在整个计算机科学领域享有崇高的声望，属于公认难度最高的会议之一。与人工智能不同，计算机理论领域被认为是国内学界与全球顶级水平相距较大的方向，在 STOC 大会中，2000-2017 年大陆研究机构平均每年发表的论文数量仅为 0.89 篇。

该会议由 ACM SIGACT (Special Interest Group in Algorithms and Computation Theory) 主办，历年会议涵盖的领域十分广泛，包括算法和数据结构、计算复杂性、密码学、计算几何、组合学、随机与去随机化、算法博弈论和量子计算等。因新冠疫情影响，STOC 2020 于 2020 年 6 月 22-26 日在线举行。

在中国计算机学会（CCF）最新版的推荐学术会议列表，以及清华大学发表的新版计算机学科推荐学术会议和期刊列表中，STOC 均被列为 A 类会议。

论文链接：https://dl.acm.org/doi/10.1145/3357713.3384234

这篇最佳论文由吴克文与 Ryan Alweiss、Shachar Lovett、Jiapeng Zhang 合作完成，主题是「太阳花引理的改进」。

成果概述

太阳花（sunflower）是一种常见的组合结构，它表示若干两两相交均相同的集合。太阳花引理证明了，当我们有“足够多”大小不超过 w 的集合时，我们必能从中找到太阳花。自1960年由 Erdős, Rado 提出以来，尽管经历了诸多改进，太阳花引理中的“足够多”一直处于 w^w 量级。

在吴克文等人的论文中，他们将它改进到约 (log w)^w，更接近猜想的 O(1)^w。由于太阳花结构的普遍性，该引理在计算机科学与组合数学中都有很多应用。本工作由吴克文与 Ryan Alweiss, Shachar Lovett, Jiapeng Zhang 合作完成。

决策表（decision list）是一种常见的布尔函数，它可以简便地写为 if-else 嵌套代码段。决策表压缩的结果表明，给定一个任意长的 if-else 代码段，如果每个 if 中依赖的变量都不太多，那么我们可以用一个“长度可控”的 if-else 代码段来近似它，且每个 if 中依赖的变量依然不多。在吴克文等人的论文中，他们对“长度可控”证明了渐进意义上紧的界，并证实了2013年由 Gopalan, Meka, Reingold 提出的析取范式压缩的猜想，同时提供了若干在布尔函数分析、学习理论中的应用。本工作由吴克文与 Shachar Lovett, Jiapeng Zhang 合作完成。

这两份工作均遵从“结构性 vs 随机性”的分析方式，其证明核心均为使用编码/解码的技术证明概率不等式，可以看作新的交换引理（switching lemma）。

除了这篇论文之外，吴克文参与的另一篇论文——《Decision list compression by mild random restrictions（利用随机赋值的决策表压缩）》也被 STOC 2020 接收。

论文链接：https://dl.acm.org/doi/10.1145/3357713.3384241

此前，2016 年才有第一名国内本科生以一作形式在 STOC 上发表论文，他是来自清华姚班、计科 20 班的本科生钟沛林，其论文是《分布流模型中的最优主成分分析》（Optimal Principal Component Analysis in Distributed and Streaming Models）。

吴克文之前，也曾有国人在 STOC 大会上获奖。在去年的 STOC 2019 大会上，来自麻省理工学院的陈立杰获得了最佳学生论文奖。

关于吴克文

研究经历

吴克文，北京大学信息科学技术学院计算机科学与技术方向2016级本科生。

在大一暑假，他有幸选入首届图灵班。出于对数学的兴趣，他于大二开始同时进行数学双学位的学习。

在体验过多个不同方向的实验室之后，他最终选择了理论计算机作为科研方向，并加入中科院计算所孙晓明老师的课题组开展科研练习。期间，他学习了前沿计算理论知识，并参与了若干复杂性理论、算法设计课题，逐步熟悉了该领域的科研特点。相关科研成果发表于SODA、ICALP、TCAD、COCOON。

在大三暑假，由孙晓明老师推荐，他前往UCSD跟从Shachar Lovett教授进行暑期科研。在大约三个月的科研期间，他借机在美国参加了STOC、CCC会议，并于会上与诸多理论计算机科研工作者进行交流学习。此外，他以“结构性vs随机性”为主题开展科研学习，有幸利用相关技术推进了“决策表压缩”和“太阳花引理”的研究。其中，后者的改进也受到组合数学科研工作者的关注，并有Quanta杂志及国内自媒体进行报道。相关科研成果发表于STOC。

本科毕业后，他将加入UC Berkeley继续进行相关领域的研究。

吴克文同学在学习与科研上的成果也得到了学院、学校的认可：本科入学以来，他获得了五四奖学金、北京大学一等奖学金、中石油奖学金、三好学生等多项荣誉。此外，他还参与若干大学生程序设计竞赛并获得了若干奖项，如国际大学生程序设计竞赛河内赛区银牌等。

参考链接：https://mp.weixin.qq.com/s/bpC3FweuEtJZHRQJc7B3iQ

来源：北大信科研会、机器之心  参与：泽南

你会关注

秘密：一半家长要求孩子成绩班级前三名，你说有多少会失望？ 今天我们怎样做家长                                                                           欢迎转发      

---

欢迎投稿原创稿件，欢迎媒体选用，转载需与本公号联系

评论是一种态度，评论是一种思想，评论应该是一种正能量。

科教评论，聚集有温度的评论！

点个“在看”再走吧