近日，北京大学信息科学技术学院16级图灵班学生吴克文在计算机科学领域顶级国际会议，第52届ACM计算理论年会（52nd Annual Symposium on the Theory of Computing，STOC 2020）上发表《太阳花引理的改进（Improved bounds for the sunflower lemma）》和《利用随机赋值的决策表压缩（Decision list compression by mild random restrictions）》两篇论文。
前者同时荣获会议最佳论文奖。太阳花（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）。吴克文是北京大学信息科学技术学院图灵班16级本科生，科研兴趣为理论计算机，如：复杂性理论、算法设计与分析、密码学等。
作为图灵班第一届毕业生，他将前往UC Berkeley继续学习。ACM计算理论年会（STOC）是理论计算机科学领域最顶级的国际会议之一，在整个计算机科学领域享有崇高的声望，属于公认难度最高的会议之一。
该会议由ACM SIGACT (Special Interest Group in Algorithms and Computation Theory)主办，历年会议涵盖的领域十分广泛，包括算法和数据结构、计算复杂性、密码学、计算几何、组合学、随机与去随机化、算法博弈论和量子计算等。因新冠疫情影响，STOC 2020于2020年6月22-26日在线举行。
《太阳花引理的改进》论文链接：https://dl.acm.org/doi/10.1145/3357713.3384234《利用随机赋值的决策表压缩》论文链接：https://dl.acm.org/doi/10.1145/3357713.3384241