Robert Andrews, Institute for Advanced Study

Abstract

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 of two polynomials in O(log n) parallel time by using a combination of polynomial interpolation and Newton's identities for symmetric polynomials. No background in algebra is required.

Based on joint work with Avi Wigderson.

See: https://theory.cs.rutgers.edu/theory_seminar