Seminar • Algorithms and Complexity • Constant-Depth Arithmetic Circuits for Linear Algebra Problems

Please note: This seminar will take place in DC 2306 and online.

Robert Andrews, Postdoctoral Researcher
School of Mathematics, Institute for Advanced Study, Princeton

How do you compute the greatest common divisor (GCD) of two univariate polynomials? The Euclidean algorithm provides a polynomial-time solution, and fast variants of the Euclidean algorithm can solve this problem in nearly-linear time. 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 in parallel 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. In fact, this algorithm can be implemented as an arithmetic circuit of constant depth. Similar ideas yield constant-depth circuits to compute the resultant, Bézout coefficients, and squarefree decomposition.

Based on joint work with Avi Wigderson.

To attend this seminar in person, please go to DC 2306. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/98836628413.