北大图灵班本科生吴克文获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

产业最佳论文顶会论文STOC

相关数据

人工智能技术

在学术研究领域，人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体（intelligent agent）

来源：Russell, S., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach.

博弈论技术

博弈论，又译为对策论，或者赛局理论，应用数学的一个分支，1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》，标志着现代系统博弈理论的的初步形成，因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

来源：维基百科

主成分分析技术

在多元统计分析中，主成分分析（Principal components analysis，PCA）是一种分析、简化数据集的技术。主成分分析经常用于减少数据集的维数，同时保持数据集中的对方差贡献最大的特征。这是通过保留低阶主成分，忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面。但是，这也不是一定的，要视具体应用而定。由于主成分分析依赖所给数据，所以数据的准确性对分析结果影响很大。

来源：机器之心维基百科

量子计算技术

量子计算结合了过去半个世纪以来两个最大的技术变革：信息技术和量子力学。如果我们使用量子力学的规则替换二进制逻辑来计算，某些难以攻克的计算任务将得到解决。追求通用量子计算机的一个重要目标是确定当前经典计算机无法承载的最小复杂度的计算任务。该交叉点被称为「量子霸权」边界，是在通向更强大和有用的计算技术的关键一步。

来源：活在实验室还是实现霸权？揭开当前量子计算技术进展之谜|机器之心

合合信息机构

http://www.zhaodao.info

北京大学机构

北京大学创办于1898年，初名京师大学堂，是中国第一所国立综合性大学，也是当时中国最高教育行政机关。辛亥革命后，于1912年改为现名。2000年4月3日，北京大学与原北京医科大学合并，组建了新的北京大学。原北京医科大学的前身是国立北京医学专门学校，创建于1912年10月26日。20世纪三、四十年代，学校一度名为北平大学医学院，并于1946年7月并入北京大学。1952年在全国高校院系调整中，北京大学医学院脱离北京大学，独立为北京医学院。1985年更名为北京医科大学，1996年成为国家首批“211工程”重点支持的医科大学。两校合并进一步拓宽了北京大学的学科结构，为促进医学与人文社会科学及理科的结合，改革医学教育奠定了基础。

官网，http://www.pku.edu.cn/