编者按
近日,北京大学信息科学技术学院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
— 版权声明 —
本内容由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料,版权属北京大学前沿计算研究中心微信所有;从公开渠道收集、整理及授权转载的文字、图片和音视频资料,版权属原作者。本公众号内容原作者如不愿意在本号刊登内容,请及时通知本号,予以删除。
点击 阅读原文 ,查看更多精彩!
喜欢本篇内容,请点 在看
以上所述就是小编给大家介绍的《北京大学图灵班本科生获STOC最佳论文奖》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 来自本科生的暴击:清华开源「天授」强化学习平台,纯PyTorch实现
- 通过生产者与消费者模型感受死锁——西邮本科生的实验
- 在《我的世界》里从零打造一台计算机有多难?复旦本科生大神花费了一年心血
- 中国学霸本科生提出AI新算法:速度比肩Adam,性能媲美SGD,ICLR领域主席赞不绝口
- python图灵机器人
- 重塑金融体系,图灵奖得主的区块链平台开放公测
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
计算机科学概论(第7版) (平装)
J.Glenn Brookshear / 王保江 / 人民邮电出版社 / 2003-9 / 49.0
《计算机科学概论(第2版)》更新了部分内容,使其更加贴近于计算机科学领域内的最新趋势,这包括了网络安全、开源运动、关联存储、公钥加密、XML、Java和C#等内容。扩充了网络和Internet所覆盖的内容。一个程序用C#语言编写,还有C、C++和Java,作为语言的例子。不过整个方法依旧保持语言的独立。一起来看看 《计算机科学概论(第7版) (平装)》 这本书的介绍吧!