Let $R = \mathbb{F}[x_1, x_2, \ldots, x_n]$. For a polynomial $f \in R[y]$, we say that a polynomial $p\in R$ is a root of $f$, if $f(p) = 0$. We study the relation between the arithmetic circuit sizes of $f$ and $p$ for general circuits and algebraic branching programs. An algebraic branching program (ABP) is given by a layered directed acyclic graph with source $\sigma$ and sink $\tau$, whose edges are labeled by variables or field constants. It computes the sum of weights of all paths from $\sigma$ to $\tau$, where the weight of a path is defined as the product of edge-labels on the path. For the size of an ABP we count the number of nodes in the underlying graph.

We address the following fundamental question: suppose the polynomial $f$ can be computed by an ABP of size $s$. Is the ABP size of every root $p$ of $f$ guaranteed to be bounded by a polynomial in $s$ ? For general circuits it is known that the circuit size of any root $p$
of a polynomial $f$ with circuit size $s$ is at most $poly(s,deg(p),m)$, where $m$ is the multiplicity of $p$ in $f$, i.e. $m$ is the largest number such that $(p-y)^m$ divides $f$. This bound follows from a result about factors of arithmetic circuits
independently obtained by Kaltofen and Buergisser.

In this paper, we study the above question for ABPs for the case where $f$ is assumed to factor as $f = p_0 \cdot (p_1 - y)(p_2 - y) \ldots (p_r -y)$, for $p_0, p_1, \ldots, p_r \in \F[x_1, x_2, \ldots, x_n]$ with $p_0 \neq 0$ and $|\{p_1, p_2, \ldots, p_r\}| = r$, and where $p_1$ is {\em degree-dominant} in the sense that $mindeg(p_1) > max_{2 \leq i \leq r} deg(p_i)$. For this situation, provided $\F$ has characteristic zero, we show that $p_1$ can be computed by an ABP of size polynomial in $s$.

To prove the above result, we view the question as a problem of computing eigenvalues. Roughly, the $p_is$ are made to appear as the eigenvalues of some matrix over the field $\mathbb{F}(x_1, x_2, \ldots, x_n)$ of rational functions. This problem is then solved by adapting the numerical method of power iteration to our situation. Using power iteration makes the computation amenable to be coded out as an ABP, since ABPs can efficiently compute iterated matrix multiplication.

In this work we adapt techniques which are well-known from numerical analysis, for use in the area of arithmetic circuit complexity. Staying with this theme, we also improve the above mentioned $poly(s, deg(p),m)$ bound for the circuit size of a root $p$ of a polynomial $f$ computed by an (unrestricted) arithmetic circuit of size $s$. For this we develop a discrete analogue of Newton's Method.

Let $R = \F[x_1, x_2, \ldots, x_n]$. For a polynomial $f \in R[y]$, we say that a polynomial $p\in R$ is a {\em root} of $f$, if $f(p) = 0$. We study the relation between the arithmetic circuit sizes of $f$ and $p$ for general circuits and algebraic branching programs.

We address the following fundamental question: suppose the polynomial $f$ can be computed by an ABP of size $s$. Is the ABP size of every root $p$ of $f$ guaranteed to be bounded by a polynomial in $s$ ? For general circuits it is known that the circuit size of any root $p$ of a polynomial $f$ with circuit size $s$ is at most $poly(s,deg(p),m)$, where $m$ is the {\em multiplicity} of $p$ in $f$, i.e. $m$ is the largest number such that $(p-y)^m$ divides $f$. This bound follows from a result about factors of arithmetic circuits independently obtained by Kaltofen and B\"{u}rgisser.

In this paper, we study the above question for ABPs for the case where $f$ is assumed to factor as $f = p_0 \cdot (p_1 - y)(p_2 - y) \ldots (p_r -y)$, for $p_0, p_1, \ldots, p_r \in \F[x_1, x_2, \ldots, x_n]$ with $p_0 \neq 0$, and where $p_1$ is {\em degree-dominant} in the sense that $mindeg(p_1) > max_{2 \leq i \leq r} deg(p_i)$. For this situation, provided $\F$ has characteristic zero, we show that $p_1$ can be computed by an ABP of size polynomial in $s$.

To prove the above result, we view the question as a problem of computing eigenvalues. Roughly, the $p_is$ are made to appear as the eigenvalues of some matrix over the field $\F(x_1, x_2, \ldots, x_n)$ of rational functions. This problem is then solved by adapting the numerical method of power iteration to our situation. Using power iteration makes the computation amenable to be coded out as an ABP, since ABPs can efficiently compute iterated matrix multiplication.

In this work we adapt techniques which are well-known from numerical analysis, for use in the area of arithmetic circuit complexity. Staying with this theme, we also improve the above mentioned $poly(s, deg(p),m)$ bound for the circuit size of a root $p$ of a polynomial $f$ computed by an (unrestricted) arithmetic circuit of size $s$. For this we develop a discrete analogue of Newton's Method.

The previous version of the paper erroneously stated Theorem 1 to work soly assuming $p_1, p_2, \ldots, p_r$ are distinct polynomials. This has been corrected. In addition the proof has been slightly simplified by avoiding the extra complication of using homogenization.

For two polynomials $f \in \mathbb{F}[x_1, x_2, \ldots, x_n, y]$ and $p \in \mathbb{F}[x_1, x_2, \ldots, x_n]$, we say that $p$ is a root of $f$, if $f(x_1, x_2, \ldots, x_n, p) \equiv 0$. We study the relation between the arithmetic circuit sizes of $f$ and $p$ for general circuits and skew circuits. Arithmetic skew circuits are defined by restricting every multiplication gate to have at least one of its inputs equal to a variable or a field constant. They were introduced by Toda, who showed they capture the complexity of the determinant polynomial.

We address the following fundamental question: suppose the polynomial $f$ can be computed by a skew circuits of size $s$. Is the skew circuit size of every root $p$ of $f$ guaranteed to be bounded by a polynomial in $s$ ? For general circuits it is known that the circuit size of any root $p$ of a polynomial $f$ with circuit size $s$ is at most $poly(s,deg(p),m)$, where $m$ is the multiplicity of $p$ in $f$, i.e. $m$ is the largest number such that $(p-y)^m$ divides $f$. This bound follows from a result about factors of arithmetic circuits independently obtained by Kaltofen and Buergisser.

In this paper, we study the above question for skew circuits for the canonical case where $f$ is assumed to factor as

$f = p_0 \cdot (p_1 - y)(p_2 - y) \ldots (p_r -y)$,

for $p_0, p_1, \ldots, p_r \in \mathbb{F}[x_1, x_2, \ldots, x_n]$ with $p_0 \not\equiv 0$, and where $p_1, p_2, \ldots, p_r$ are pairwise distinct, i.e. all multiplicities are one. Our main result is that for this situation, provided the field $\mathbb{F}$ has characteristic zero, any root $p_i$ can be computed by a skew circuit of size polynomial in $s$. This demonstrates an important special case where the answer to the above mentioned question is affirmative. Prior to this paper, no method was known to provide a $poly(s)$ bound for this main scenario.

To prove the above result, we view the question as a problem of computing eigenvalues. Roughly, the $p_is$ are made to appear as the eigenvalues of some matrix over the field $\mathbb{F}(x_1, x_2, \ldots, x_n)$ of rational functions. This problem is then solved by adapting the numerical method of power iteration to our situation. Using power iteration makes the computation amenable to be coded out as a skew circuit, since skew circuits can efficiently compute iterated matrix multiplication.

A novel aspect of this work is that we adapt techniques which are well-known from numerical analysis, for use in the area of arithmetic circuit complexity. Staying with this theme, we also improve the above mentioned $poly(s, deg(p),m)$ bound for the circuit size of a root $p$ of a polynomial $f$ computed by an (unrestricted) arithmetic circuit of size $s$. For this we develop a discrete analogue of Newton's Method.