Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

Autor: Maurice J. Jansen
Rok vydání: 2010
Předmět:
Zdroj: Theory of Computing Systems. 49:343-354
ISSN: 1433-0490
1432-4350
DOI: 10.1007/s00224-010-9308-1
Popis: The determinantal complexity of a polynomial f(x 1,x 2,…,x n ) is the minimum m such that f=det m (L(x 1,x 2,…,x n )), where L(x 1,x 2,…,x n ) is a matrix whose entries are affine forms in the x i s over some field $\mbox {$\mathbb {F}$}$. Asymptotically tight lower bounds are proven for the determinantal complexity of the elementary symmetric polynomial $S^{d}_{n}$ of degree d in n variables, 2d-fold iterated matrix multiplication of the form 〈u|X 1 X 2…X 2d |v〉, and the symmetric power sum polynomial $\sum_{i=1}^{n} x_{i}^{d}$, for any fixed d>1. A restriction of determinantal computation is considered in which the underlying affine map λx.L(x) must satisfy a rank lowerability property: L mapping to m×m matrices is said to be r-lowerable, if there exists an $a\in \mbox {$\mathbb {F}$}^{n}$ such that rank (L(a))≤m−r. In this model strongly nonlinear and exponential lower bounds are proved for several polynomial families. For example, for $S^{2d}_{n}$ it is proved that the determinantal complexity using r-lowerable maps is Ω(n d/(2d−r)), for constants d and r with 2≤d+1≤r
Databáze: OpenAIRE
Externí odkaz: