Get all the updates for this publication

Conferences

Arithmetic circuit lower bounds via MaxRankOpen Access

Published in

2013

Volume: 7965 LNCS

Issue: PART 1

Pages: 661 - 672

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial 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 x n requires Ω(nd-1/2d) size. This improves the lower bounds in [9] for d = ω(1). - As our second main result, we show that there is an explicit polynomial on n variables and degree at most n/2 for which any depth-3 circuit C of product dimension at most n/10 (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 [14]. 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 [11]. - 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 [7]. © 2013 Springer-Verlag.

Topics: Upper and lower bounds (56)%56% related to the paper, Affine arithmetic (53)%53% related to the paper, Dimension (graph theory) (52)%52% related to the paper, Product (mathematics) (52)%52% related to the paper and Multilinear map (51)%51% related to the paper

View more info for "Arithmetic circuit lower bounds via maxrank"

Preprint Version

Content may be subject to copyright.This is a green open access articleThis is a green open access article

About the journal

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

ISSN | 03029743 |

Open Access | Yes |

Concepts (13)

- Arithmetic circuit
- Branching programs
- Complexity measures
- DEPTH-3 CIRCUITS
- MAXIMUM RANK
- Multivariate polynomial
- Polynomial coefficients
- VARIABLE SUBSTITUTION
- AUTOMATA THEORY
- Integrating circuits
- Logic circuits
- Polynomials
- Matrix algebra