北大图灵班本科生吴克文获STOC 2020最佳论文奖

机器之心报道

参与：泽南

今天，北京大学前沿计算研究中心官方公众号报道称，在全球计算机理论顶会 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 类会议。

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

论文链接： 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。

由于太阳花结构的普遍性，该引理在计算机科学与组合数学中都有很多应用。

除了这篇论文之外，吴克文参与的另一篇论文——《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 大会上，来自麻省理工学院的陈立杰获得了最佳学生论文奖。

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

WAIC 2020 黑客马拉松由世界人工智能大会组委会主办，张江集团、优必选科技、软银集团旗下软银机器人、Watson Build 创新中心、机器之心联合承办，受到新冠疫情的影响，比赛将于 7 月 8 日 - 11 日期间以远程和小规模线下结合的方式举办，招募全球顶级开发者同台竞技。

点击图片或「阅读原文」搭乘参赛