Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-080 | 16th April 2024 21:37

Constant-Depth Arithmetic Circuits for Linear Algebra Problems


Authors: Robert Andrews, Avi Wigderson
Publication: 20th April 2024 05:21
Downloads: 189


We design polynomial size, constant depth (namely, $AC^0$) 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$ 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 $AC^0$ arithmetic circuits. Here too we solve problems such as computing the GCD and squarefree decomposition in $AC^0$.

ISSN 1433-8092 | Imprint