Computer Science/Discrete Mathematics Seminar II

Given two univariate polynomials, how does one compute their greatest common divisor (GCD)? This problem can be solved in polynomial time using the Euclidean algorithm, and even in quasi-linear time using a fast variant of the Euclidean algorithm. The GCD can also be expressed in a linear-algebraic form. Basic tasks in linear algebra like computing determinants and solving linear systems can be performed in $O(\log^2 n)$ parallel time, and this can be used to compute the GCD in $O(\log^2 n)$ parallel time. This algorithm does not take advantage of any structure present in the resulting linear systems, so in principle one could compute the GCD even faster.

In this talk, I will describe a new algorithm that computes the GCD in $O(\log n)$ parallel time by using a combination of polynomial interpolation and Newton's identities for symmetric polynomials. Similar ideas yield $O(\log n)$ parallel time algorithms to compute the resultant, Bézout coefficients, and squarefree decomposition.

Based on joint work with Avi Wigderson.