北京大学图灵班本科生获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

—   版权声明  —

本内容由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点击 阅读原文 ，查看更多精彩！

喜欢本篇内容，请点在看