Seminar Details
Parallel Computation of Greatest Common Divisors of Polynomials
- Start Date: February 28, 2024
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Robert Andrews - Institute for Advanced Study
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
- Presentation Type: Stand Alone Presentation
- 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.