pdf icon
Volume 7 (2011) Article 8 pp. 119-129
Arithmetic Complexity in Ring Extensions
Received: May 25, 2009
Published: May 9, 2011
Download article from ToC site:
[PDF (184K)] [PS (670K)] [Source ZIP]
Keywords: algebraic complexity, algebraic extensions
ACM Classification: F.2.1
AMS Classification: 03D15

Abstract: [Plain Text Version]

$\newcommand\field{{\mathbb F}}$ Given a polynomial $f$ with coefficients from a field $\field$, is it easier to compute $f$ over an extension ring $R$ than over $\field$? We address this question, and show the following. For every polynomial $f$, there is a noncommutative extension ring $R$ of the field $\field$ such that $\field$ is in the center of $R$ and $f$ has a polynomial-size formula over $R$. On the other hand, if $\field$ is algebraically closed, no commutative extension ring $R$ can reduce formula or circuit complexity of $f$. To complete the picture, we prove that over any field, there exist hard polynomials with zero-one coefficients. (This is a basic theorem, but we could not find it written explicitly.) Finally, we show that low-dimensional extensions are not very helpful in computing polynomials. As a corollary, we obtain that the elementary symmetric polynomials have formulas of size $n^{O(\log \log n)}$ over any field, and that division gates can be efficiently eliminated from circuits, over any field.