Paper Info
Title
On the size of homogeneous and of depth four formulas with low individual degree.
Abstract
Let r be an integer. Let us call a polynomial f 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. Specifically, first define the formal degree of a node a with respect to a variable x inductively as follows. For a leaf it is 1 if a is labelled with x 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. 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.
Year
DOI
Venue
2016
10.1145/2897518.2897550
STOC '16: Symposium on Theory of Computing Cambridge MA USA June, 2016
Keywords
DocType
ISSN
arithmetic circuits,elementary symmetric polynomials,individual degree,Iterated Matrix Multiplication,log product,lower bounds,shifted partials
Conference
0737-8017
ISBN
Citations 
PageRank 
978-1-4503-4132-5
2
0.38
References 
Authors
0
3
Name
Order
Citations
PageRank
Neeraj Kayal126319.39
Chandan Saha222716.91
Sébastien Tavenas3145.19