查看原文
其他

【直播】【QuACT系列报告】清华大学杨天祺:3.1n - o(n) Circuit Lower Bounds for...

KouShare 蔻享学术 2021-05-20


本系列报告由中国科学院计算技术研究所主办,于2021年5月20日10:00开始,授权蔻享学术进行网络直播。




直播二维码


3.1n - o(n) Circuit Lower Bounds for Explicit Functions

报告人


杨天祺(清华大学)

时间


2021年5月20日 10:00-11:00


Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function ‍‍f=IFn2→IF2 requires circuit of size ‍‍Ω2n/n by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in ‍‍NP) not computable by circuits of size ‍‍10n. In fact, a ‍‍3n-o(n) explicit lower bound by Blum (TCS, 1984) was unbeaten for over 30 years until a recent breakthrough by Find et al. (FOCS, 2016), which proved a ‍‍(3+1/86)n-o(n) lower bound for affine dispersers, a class of functions known to be constructible in P. In this talk, I will show a stronger lower bound ‍‍3.1n-o(n) for affine dispersers. To get this result, I will show how to strengthen the gate elimination approach for ‍‍(3+1/86)n lower bound, by a more sophisticated case analysis that significantly decreases the number of bottleneck structures introduced during the elimination procedure. Intuitively, this improvement relies on three observations: adjacent bottleneck structures become less troubled; the gates eliminated are usually connected; and the hardest cases during gate elimination have nice local properties to prevent the introduction of new bottleneck structures.This is a joint work with Jiatu Li.


报告人简介


图 | 杨天祺




Tianqi Yang is a sophomore at Institute for Interdisciplinary Information Sciences, Tsinghua University. His research interests are in computational complexity, and is currently focusing on circuit lower bounds.




QuACT系列报告】专题链接:https://www.koushare.com/frontiers/fop/intro

编辑:黄琦



往期回顾











为满足更多科研工作者的需求,蔻享平台开通了各科研领域的微信交流群。进群请添加微信18019902656(备注您的科研方向)小编拉您入群哟!
蔻享网站www.koushare.com已开通自主上传功能,期待您的分享!

欢迎大家提供各类学术会议或学术报告信息,以便广大科研人员参与交流学习。

联系人:李盼 18005575053(微信同号)

戳这里,观看精彩直播哟!

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存