Constant-Depth Arithmetic Circuits for Linear Algebra Problems

We design polynomial size, constant depth (namely, AC 0 F ) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Our GCD algorithm extends to any number of polynomials. Previously, the best known arithmetic formulae for these problems required super-polynomial size, regardless of depth.

These results are based on new algorithmic techniques to compute various symmetric functions in the roots of polynomials, as well as manipulate the multiplicities of these roots, without having access to them. These techniques allow AC 0 F computation of a large class of linear and polynomial algebra problems, which include the above as special cases.

We extend these techniques to problems whose inputs are multivariate polynomials, which are represented by constant-depth arithmetic circuits. Here too we solve problems such as computing the GCD and squarefree decomposition in AC 0 F .

1 A minor but important point which should be mentioned is that arithmetic circuits formally cannot compute discontinuous functions like GCD, and one has to add to them (as is standard in the field) the ability of branching on testing of a given field element is zero or not.

2 Toeplitz matrices have constant diagonals. 3 The reader unfamiliar with this gem is encouraged to find any efficient algorithm for them.