Please note: This seminar will take place in DC 1304 and online.
Shanthanu Rai, PhD student
School of Technology and Computer Science, Tata Institute of Fundamental Research
The Euclidean algorithm for computing the greatest common divisor (GCD) is arguably the oldest non-trivial algorithm in print. Originally described for integers, it also applies to univariate polynomials. While efficient, the Euclidean algorithm is inherently sequential. Can it be implemented efficiently in parallel for polynomials?
In their seminal work, Andrews and Wigderson answered this affirmatively: they showed that the GCD of two univariate polynomials can be computed in constant parallel time in the arithmetic PRAM model. Equivalently, in algebraic-complexity terms, they proved that the GCD can be computed in (piecewise) algebraic circuits of constant depth and polynomial size. However, their results hold only over fields of characteristic zero and fields of large (polynomially bounded) characteristic.
In this work, we extend their result to all sufficiently large fields, regardless of characteristic. The key ingredient is an analogue of the fundamental theorem of symmetric polynomials for constant-depth algebraic circuits, strengthening a result of Bläser and Jindal for unbounded-depth circuits. Our approach crucially uses the factor closure property of constant-depth circuits, established in our earlier work.
Based on joint work with Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi and Shubhangi Saraf.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.