文章基本信息

标题：On the size of homogeneous and of depth four formulas with low individual degree
本地全文：下载
作者：Neeraj Kayal ; Chandan Saha ; Sébastien Tavenas 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2015
卷号：2015
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let r 1 be an integer. Let us call a polynomial f ( x 1 x 2 x N ) F [ x ] as 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 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. Specifically, first define the formal degree of a node with respect to a variable x i inductively as follows. For a leaf it is 1 if is labelled with x i and zero otherwise; for an internal node labelled with (respectively + ) it is the sum of (respectively the maximum of) the formal degrees of the children with respect to x i . We call an arithmetic circuit as a multi- r -ic circuit if the formal degree of the output node with respect to any variable is at most r . We prove lower bounds for various subclasses of multi- r -ic circuits, including: 1. An N ( log N ) lower bound against homogeneous multi- r -ic formulas (for an explicit multi- r -ic polynomial on N variables). 2. A n r 1 1 r d lower bound against depth four multi- r -ic circuits computing the polynomial IMM n d corresponding to the product of d matrices of size n n each. 3. A 2 N lower bound against depth four multi- r -ic circuits computing an explicit multi- r -ic polynomial on N variables.
关键词：arithmetic circuits ; elementary symmetric polynomials ; individual degree ; Iterated Matrix Multiplication ; log product ; lower bounds ; shifted partials