摘要：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.
