Published: May 9, 2011
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.
Licensed under a Creative Commons Attribution License (CC-BY)