Theory of Computing ------------------- Title : Arithmetic Complexity in Ring Extensions Authors : Pavel Hrubes and Amir Yehudayoff Volume : 7 Number : 8 Pages : 119-129 URL : https://theoryofcomputing.org/articles/v007a008 Abstract -------- Given a polynomial f with coefficients from a field F, is it easier to compute f over an extension ring R of F than over F? We address this question, and show the following. For every polynomial f, there is a noncommutative extension ring R of the field F such that F is in the center of R and f has a polynomial-size formula over R. On the other hand, if F 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.