Introduction : Motivation to study algorithmic problems related to polynmials - overview of example applications. The language - Rings, Fields, Ideals, and Polynomials. (This course does not assume the basics on these, but instead it will teach required the basics).
Algorithms for Polynomials . Algorithm for GCD: Euclid's algorithm. Hilbert's basis theorem. Solving polynomial equations; ideal membership problem; Grobner bases: Buchberger's algorithm. Polynomial factorization over finite Fields: Cantor Zassenhaus Algorithm, applications to root finding. Hensel lifting and applications to polynomial factorization: Zassenhaus Algorithm. Lattices, and LLL algorithm for basis reduction.
Complexity of Polynomials: Basic Arithmetic Circuit Complexity. Polynomial Identity Testing problem; Applications to Primality Testing: AKS Primality test; Introduction to Algebraic Complexity. Polynomial and Matrix Multiplication Problems, Permanent vs Determinant problem and connections to Polynomial Identity Testing.
Text Books
Modern Computer Algebra- Joachim von Zur Gathen and Juergen Gerhard
