Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
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.