【直播】【QuACT系列报告】清华大学杨天祺:3.1n - o(n) Circuit Lower Bounds for...
本系列报告由中国科学院计算技术研究所主办,于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.
报告人简介
编辑:黄琦
往期回顾
欢迎大家提供各类学术会议或学术报告信息,以便广大科研人员参与交流学习。