Get all the updates for this publication

Articles

Arithmetic circuit lower bounds via maximum-rank of partial derivative matricesPublished in Association for Computing Machinery

2016

DOI: 10.1145/2898437

Volume: 8

Issue: 3

We introduce the polynomial coefficient matrix and identify the maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove superpolynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results: —As our first main result, we prove that any homogeneous depth-3 circuit for computing the product of d matrices of dimension n × n requires (nd −1/2d) size. This improves the lower bounds in Nisan and Wigderson [1995] for d = ω(1). —As our second main result, we show that there is an explicit polynomial on n variables and degree at most2 n for which any depth-3 circuit of product dimension at most10 n (dimension of the space of affine forms feeding into each product gate) requires size 2(n). This generalizes the lower bounds against diagonal circuits proved in Saxena [2008]. Diagonal circuits are of product dimension 1. —We prove a n(log n) lower bound on the size of product-sparse formulas. By definition, any multilinear formula is a product-sparse formula. Thus, this result extends the known super-polynomial lower bounds on the size of multilinear formulas [Raz 2006]. —We prove a 2(n) lower bound on the size of partitioned arithmetic branching programs. This result extends the known exponential lower bound on the size of ordered arithmetic branching programs [Jansen 2008]. c 2016 ACM

Topics: Upper and lower bounds (57)%57% related to the paper, Affine arithmetic (54)%54% related to the paper, Matrix (mathematics) (53)%53% related to the paper, Multilinear map (52)%52% related to the paper and Polynomial (52)%52% related to the paper

View more info for "Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices"

Content may be subject to copyright.

About the journal

Journal | Data powered by TypesetACM Transactions on Computation Theory |
---|---|

Publisher | Data powered by TypesetAssociation for Computing Machinery |

ISSN | 19423454 |

Open Access | No |

Concepts (12)

- Logic circuits
- Polynomials
- Timing circuits
- Arithmetic circuit
- Branching programs
- Complexity measures
- Multivariate polynomial
- Partial derivatives
- Polynomial coefficients
- SUPER-POLYNOMIALS
- VARIABLE SUBSTITUTION
- Matrix algebra