Arithmetic circuit lower bounds via MaxRank

DOI10.1007/978-3-642-39206-1_56MaRDI QIDQ5326600zbMATH OpenOpenAlexFDO

Authors Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma M. N.

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.3308

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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 main result, we prove that any homogeneous depth-3 circuit for computing the product of $d$ matrices of dimension $nimesn$ requires $Omega(n^{d-1}/2^d)$ size. This improves the lower bounds by Nisan and Wigderson(1995) when $d=omega(1)$. There is an explicit polynomial on $n$ variables and degree at most $fracn2$ for which any depth-3 circuit $C$ of product dimension at most $fracn10$ (dimension of the space of affine forms feeding into each product gate) requires size $2^{Omega(n)}$. This generalizes the lower bounds against diagonal circuits proved by Saxena(2007). Diagonal circuits are of product dimension 1. We prove a $n^{Omega(logn)}$ lower bound on the size of product-sparse formulas. By definition, any multilinear formula is a product-sparse formula. Thus, our result extends the known super-polynomial lower bounds on the size of multilinear formulas by Raz(2006). We prove a $2^{Omega(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 given by Jansen(2008).

Recommendations

• Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices
• Arithmetic circuits: a chasm at depth 3
• On the Complexity of Matrix Product
• Tensor-rank and lower bounds for arithmetic formulas
• scientific article; zbMATH DE number 1775446

Cited in

(16)

• Lower bounds for arithmetic circuits via the Hankel matrix
• A note on parameterized polynomial identity testing using hitting set generators
• On proving parameterized size lower bounds for multilinear algebraic models
• On the limits of depth reduction at depth 3 over small finite fields
• Arithmetic circuits: a chasm at depth 3
• Tensor-rank and lower bounds for arithmetic formulas
• Sum of products of read-once formulas
• Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices
• Barriers for rank methods in arithmetic complexity
• Lower bounds for sum and sum of products of read-once formulas
• Fast and Efficient Circuit Topologies forFinding the Maximum of n k-Bit Numbers
• Arithmetic circuits with locally low algebraic rank
• Tensor-rank and lower bounds for arithmetic formulas
• scientific article; zbMATH DE number 7650909 (Why is no real title available?)
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Lower bounds and separations for constant depth multilinear circuits

This page was built for publication: Arithmetic circuit lower bounds via MaxRank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326600)