One of the earliest known algorithms is Euclid's algorithm for computing the greatest common divisor of two natural numbers. This algorithm also extends to univariate polynomials. The algorithm is fast, but sequential in nature. In this talk, we will see some efficient parallel algorithms (via the notion of constant-depth arithmetic circuits) for some polynomial algebra problems, including the GCD. An important idea here is an efficient way to go between two well-known representations for symmetric polynomials -- the elementary symmetric polynomials and the power sum polynomials.
The talk will be based on the paper "Constant-Depth Arithmetic Circuits for Linear Algebra Problems" by Robert Andrews and Avi Wigderson.
