Theory of Computing
-------------------
Title : Arithmetic Complexity in Ring Extensions
Authors : Pavel Hrubes and Amir Yehudayoff
Volume : 7
Number : 8
Pages : 119-129
URL : http://www.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.