甘明鱼羊来自奥菲寺
量子报道| QbitAI，微信官方账号
计算理论年会(STOC)正在网上举行。
最新消息，江苏常州的一个弟弟一口气拿了两篇论文，获得了最佳论文奖。
此外，他还是本科生,第一位获得STOC最佳论文奖的中国本科生。
没错，这是理论计算机领域的顶级会议，难度和含金量都稳居STOC.第一梯队
他叫吴克文,毕业于江苏省常州高级中学。2016年考入北京大学，2017年成为北京大学图灵班第一名学生，即将成为北京大学图灵班第一名毕业生。
致力于为中国培养下一代计算机科学领军人物的国际人才培养项目——北京大学图灵班，今年开始交出自己的“答卷”:
同样出色的，不是失去隔壁的姚班。
北大学霸斩获STOC最佳论文奖
STOC是什么样的会议？作为中国计算机联合会(CCF)推荐的计算机科学理论方向A类会议，STOC、FOCS等顶级会议也被公认为计算机科学领域难度最高、含金量最高的会议。
会议由ACM SIGACT组织，涵盖算法与数据结构、计算复杂性、密码学、计算几何、组合学、随机化与去随机化、算法博弈论和量子计算等领域。
在2020年，吴发表了两篇论文。
其中，与美国普林斯顿大学Ryan Alweiss、UCSD副教授Shachar洛维特、哈佛大学博士后张嘉鹏合作的《太阳花引理的改进（Improved bounds for the sunflower lemma）》获得STOC 2020最佳论文奖.奖
论文画风长这样
向日葵是一种常见的复合结构，它代表了许多彼此相等相交的集合。1960年，数学家保罗erds和理查德拉多提出了太阳花猜想。
这个猜想和物体的几何有关。以xy平面上的点集为例，需要先确定每个集中包含的固定个数的点，然后开始随机画环，使每个环，或者每个集，都包含这个个数的点。环和环可以重叠，所以有些点可能属于多个集合。
h-arrow-right">
△图源：QuantumMagazine
Erds和Rado提出的猜想是，当绘制足够多的环时，一定会形成太阳花，要么作为不相交集出现，要么作为集合以正确的方式重叠的形式出现。
其后，他们证明了，这个“足够多”的量级是w^w。
也就是说，对包含100个点的集合来说，要确保能找到一个由3个集合组成的太阳花，需要100^100个集合。
但数学家们当时就推测，实际需要的集合数一定比w^w小得多，应该是O(1)^w。
但在之后的近60年时间中，后续的研究都没能突破w^w这个量级。
而这篇STOC 2020最佳论文，就是在这一问题上实现了重大的突破——将约束改进为约 (log w)^w。
也就是说，将原来的结果改善了一个数量级！
在这项研究中，吴克文和他的合作者们将问题分解为两种不同的场景：
第一种场景较为简单，即集合存在大量重叠的情况。
研究人员首先要确定的是，在这个系统中，是否存在一组在很大一部分集合中是共有的点。
一旦确定了这样一组点，他们就可以把对太阳花的搜索限制在包含这组点的那部分集合中。通过这种方式不断修剪，直到找到太阳花为止。
第二种场景则更为困难。研究人员需要分析的是当集合没有太多重叠时会发生什么。在这种情况下，最有可能产生太阳花的方法是设置三个不相交的集合。
其中的难点在于，要证明三个完全独立的集合隐藏在大量轻度重叠的集合中并非易事。
于是，研究人员将布尔函数运用到了这个问题中，
首先，为特定集合中的每个点分配一个标签：如果它只包含在一个集合中，则为1；否则，设为0。
如果每个输入点都是1，那么布尔函数将输出1 （真），就意味着集合中的每个点都只在那个集合中，即集合不相交。因此，一个为“真”的结果表明存在找到太阳花的正确条件。
通过严格证明这种对应关系，这篇论文证明了，(log w)^w个集合，足以确保太阳花的产生。
由于太阳花结构的普遍性，该引理在计算机科学与组合数学中都有很多应用。
另一篇论文，同样是吴克文和Shachar Lovett、Jiapeng Zhang合作的成果，《利用随机赋值的决策表压缩（Decision list compression by mild random restrictions）》。
决策表（decision list）是一种常见的布尔函数，它可以简便地写为 if-else 嵌套代码段。
决策表压缩的结果表明，给定一个任意长的 if-else 代码段，如果每个 if 中依赖的变量都不太多，那么就可以用一个“长度可控”的 if-else 代码段来近似它，且每个 if 中依赖的变量依然不多。
在这篇论文中，研究人员对“长度可控”证明了渐进意义上紧的界，并证实了2013年由 Gopalan, Meka, Reingold 提出的析取范式压缩的猜想，同时提供了若干在布尔函数分析、学习理论中的应用。
据北大前沿计算研究中心消息，作为图灵班第一届毕业生，接下来，吴克文将前往UC伯克利继续深造。
北大图灵班交答卷：创办三年，迎来首届毕业生
作为首届毕业生，吴克文的最新成果，毫无疑问展现出了北大图灵班的实力。
北大图灵班正式创办于2017年，定位是“为中国培养计算机科学界下一代领军人物的国际化人才”，对标“清华姚班”的意味再明显不过。
领衔者也是一位图灵奖得主——计算机科学领域大师约翰·霍普克罗夫特（John Hopcroft），2017年5加入北京大学信息科学技术学院，担任图灵班指导委员会主任。
在培养方案上，同样注重多学科交叉、科研实践和国际交流。吴克文同学的最新研究成果，正是其在海外交流时完成的。
与姚班不同的是，图灵班的学生并不是在高考时选拔，而是每年从大一的学生中选拔，虽然基础要求不高（2018年要求）：
1.成绩优良，已修课程绩点≥3.0。
2.已修数学A类课程（《数学分析I》和《高等代数I》）成绩≥80分，且《计算概论A》成绩 ≥85分；本学期在修《数学分析II》和《高等代数II》。
3.非信息科学技术学院的学生报名，须在校内门户提交转院（系）转专业申请。
但想要进入其中并不容易——其每年只招收不超过30人。
2018年，北大图灵班在原有计算机科学方向基础上，新增了人工智能方向，每个方向招收30人，总共不过60人。
与姚班相同的是，北大图灵班一样人才辈出：吴克文是其中代表，但不仅仅只有吴克文。
- 2018年，2016级本科生曹芃、许逸伦同学（大三）共同一作的论文被ICLR 2019接收。
- 2019年，许逸伦、曹芃共同一作的论文被NeurIPS 2019接收。
- 2019年，2016级吴润迪共同一作论文被SIGGRAPH 2019接收。
- 2020年，许逸伦和斯坦福研究学者合作的论文，以满分被ICLR 2020选为口头展示论文 (oral)。
- 2020年，2017级本科生李沛卓共同一作的论文，被SIGGRAPH 2020接收。
现在，图灵班迎来了首批毕业生，从他们频频透露出成果来看，这个答卷足够优秀。
北大图灵班未来会怎样？
我们不妨参考下2005年成立的姚班“成果”：成立以来，到2019年已培养出375名本科生，大牛如云。
鬲融、贝小辉、马腾宇、陈丹琦和吴佳俊等毕业生，已在杜克大学、南洋理工、普林斯顿和斯坦福等全球一流名校开始任教研究。
17科满分毕业的鬲融，还在2019年以其对深度学习中非凸优化的研究，对于打造更精准的神经网络极有助益，获得诺奖风向标“斯隆奖”。
工业领域，备受瞩目的AI独角兽中，就有2家“姚班附属创业公司”：旷视、小马智行。
虽然清华姚班已经有产出，北大虽然“晚”了一点，但现在势头一点不弱。
果然，中国最好的人才，给到最好的教育，一点也不输世界顶尖高校和研究机构。
清华姚班，北大图灵，上交ACM…正在成为顶尖人才培养的新形势、新潮流。
未来，待他们的毕业生走上科研、工作岗位，必将是中国算机领域新一代产学研中坚。
参考链接：
Mathematicians Begin to Tame Wild ‘Sunflower’ Problem
https://www.quantamagazine.org/mathematicians-begin-to-tame-wild-sunflower-problem-20191021/
北京大学前沿计算研究中心：北京大学图灵班本科生获STOC最佳论文奖
https://mp.weixin.qq.com/s/bpC3FweuEtJZHRQJc7B3iQ
— 完 —
量子位 QbitAI · 头条号签约
关注我们，第一时间获知前沿科技动态
