文章基本信息

标题：On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
本地全文：下载
作者：Neeraj Kayal ; Chandan Saha ; Sébastien Tavenas 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2018
卷号：14
页码：1-46
DOI：10.4086/toc.2018.v014a016
出版社：University of Chicago
摘要：Let r ≥ 1 be an integer. Let us call a polynomial f(x1, x2,..., xN) ∈ F[x] a multi-r-ic polynomial if the degree of f with respect to any variable is at most r. (This generalizes the notion of multilinear polynomials.) We investigate the arithmetic circuits in which the output is syntactically forced to be a multi-r-ic polynomial and refer to these as multi-r-ic circuits. We prove lower bounds for several subclasses of such circuits, including the following. 1. An N Ω(logN) lower bound against homogeneous multi-r-ic formulas (for an explicit multi-r-ic polynomial on N variables). 2. An (n/r 1.1 ) Ω √ d/r lower bound against depth-four multi-r-ic circuits computing the polynomial IMMn,d corresponding to the product of d matrices of size n×n each.
关键词：complexity theory; lower bounds; algebraic complexity; arithmetic formulas;; arithmetic circuits; partial derivatives