文章基本信息
- 标题：Approaching the chasm at depth four
- 本地全文：下载
- 作者：Ankit Gupta ; Pritish Kamath ; Neeraj Kayal 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2012
- 卷号：2012
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
Agrawal-Vinay (FOCS 2008), Koiran (TCS 2012) and Tavenas (MFCS 2013) have recently shown that an exp((nlogn)) lower bound for depth four homogeneous circuits computing the permanent with bottom layer of gates having fanin bounded by n translates to super-polynomial lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via such homogeneous depth four circuits with bounded bottom fanin.We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by n computing the permanent (or the determinant) must be of size exp((n)) .
- 关键词：depth-4 circuits; determinant; lower bounds; Partial derivatives; permanent
