文章基本信息

标题：Challenges in computational lower bounds
本地全文：下载
作者：Emanuele Viola
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2013
卷号：2013
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：
We draw two incomplete, biased maps of challenges incomputational complexity lower bounds. Our aim is to putthese challenges in perspective, and to present someconnections which do not seem widely known.
关键词：branching program; circuit; Communication complexity; Correlation; lower bounds; polynomial; symmetric gates