期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：For two polynomials fF[x1x2xny] and pF[x1x2xn], we say that p is a root of f, if f(x1x2xnp)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(sdeg(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=p0(p1−y)(p2−y)(pr−y),
for p0p1prF[x1x2xn] with p00 , and where p1p2pr are pairwise distinct, i.e. all multiplicities are one. Our main result is that for this situation, provided the field F has characteristic zero, any root pi 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 pis are made to appear as the eigenvalues of some matrix over the field F(x1x2xn) 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(sdeg(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.
