北京大学图灵班本科生获STOC最佳论文奖

  近日,北京大学信息科学技术学院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 继续学习。

  

关于STOC

 

  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