Name
Abstract | ||
|---|---|---|
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 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 × 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 most n/2 for which any depth-3 circuit 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 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]. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2898437 | TOCT |
Keywords | Field | DocType |
Partial derivative matrix,arithmetic circuits | Diagonal,Discrete mathematics,Combinatorics,Coefficient matrix,Exponential function,Polynomial,Matrix (mathematics),Upper and lower bounds,Affine arithmetic,Arithmetic,Multilinear map,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 3 | 1942-3454 |
Citations | PageRank | References |
1 | 0.35 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |
| Gaurav Maheshwari | 2 | 5 | 1.44 |
| Jayalal M. N. Sarma | 3 | 17 | 9.16 |