
Volume 14 (2018)
Article 16 pp. 1-46
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
Received: August 18, 2016
Revised: November 24, 2017
Published: December 6, 2018
Revised: November 24, 2017
Published: December 6, 2018
Keywords: complexity theory, lower bounds, algebraic complexity, arithmetic formulas, arithmetic circuits, partial derivatives
Categories: complexity theory, lower bounds, algebraic complexity, arithmetic formulas, arithmetic circuits, partial derivatives
ACM Classification: F.1.3, F.1.1
AMS Classification: 68Q17, 68Q15
Abstract: [Plain Text Version]
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.
- An NΩ(logN) lower bound against homogeneous multi-r-ic formulas (for an explicit multi-r-ic polynomial on N variables).
- A (n/r1.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.
- A 2Ω(√N) lower bound against depth-four multi-r-ic circuits computing an explicit multi-r-ic polynomial on N variables.
A conference version of this paper appeared in the Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC'16).