文章基本信息

标题：Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version)
本地全文：下载
作者：Noam Nisan ; Avi Wigderson
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1995
卷号：2
期号：43
出版社：Aarhus University
摘要：In this paper we describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials and iterated matrix products.