CS6842 - Algorithmic Algebra

Course Data :

Syllabus

  • 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


Reference Text Books


Pre-Requisites

    None

Parameters

Credits Type Date of Introduction
4-0-0-0-8-12 Elective Jul 2013

Previous Instances of the Course


© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits