Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods.
Maurice J. Jansen · 2010
Abstract: For two polynomials f ∈ F[x1, x2,..., xn, y] and p ∈ F[x1, x2,..., xn], we say that p is a root of f, if f(x1, x2,..., xn, 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 σ and sink τ, whose edges are labeled by variables or field constants. It computes the sum of weights of all paths from σ to τ, 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 [1] and Bürgisser [2]. In this paper, we study the above question for ABPs for the canonical case where f is assumed to factor as f = p0 · (p1 − y)(p2 − y)... (pr − y), for p0, p1,..., pr ∈ F[x1, x2,..., xn] with p0 ≡ 0, and where p1, p2,..., pr are pairwise distinct, i.e. all multiplicities are one. Our main result is that for this situation, provided F has