编者按
近日,北京大学信息科学技术学院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图灵机器人
- 重塑金融体系,图灵奖得主的区块链平台开放公测
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
逆向工程核心原理
[韩] 李承远 / 武传海 / 人民邮电出版社 / 2014-4-25 / 109.00元
本书十分详尽地介绍了代码逆向分析的核心原理。作者在Ahnlab 研究所工作多年,书中不仅包括其以此经验为基础亲自编写的大量代码,还包含了逆向工程研究人员必须了解的各种技术和技巧。彻底理解并切实掌握逆向工程这门技术,就能在众多IT 相关领域进行拓展运用,这本书就是通向逆向工程大门的捷径。 想成为逆向工程研究员的读者或正在从事逆向开发工作的开发人员一定会通过本书获得很大帮助。同时,想成为安全领域......一起来看看 《逆向工程核心原理》 这本书的介绍吧!