Events

Filters
Export this event to calendar
iCal
RSS
RSS
Close X

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Friday, December 6, 2024 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Robert Andrews

Title: Constant-Depth Arithmetic Circuits for Linear Algebra Problems

Speaker: Robert Andrews
Affiliation: University of Waterloo
Location: MC 5501

Abstract: What is the computational complexity of 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 compute the GCD in nearly-linear time. The GCD can also be expressed in a linear-algebraic form. Basic tasks in linear algebra, such as 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.