Published: May 9, 2011

**Keywords:**algebraic complexity, algebraic extensions

**Categories:**short, complexity theory, algebraic complexity, arithmetic circuits, arithmetic formulas, field extension, ring, noncommutative

**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.