Today : Tue, May 14, 2024

  • No lecture

Announcements

  • Nov 11 : End Sem on 12-11-14 2-5pm.
  • Oct 30 : Lecture will start at 4:45 today.
  • Oct 8 : Quiz-2, Date changed: Oct 15 Wed 2-3:30pm
    Syllabus Lectures 10-21.
  • Older announcements.
Back to Courses

Basic Information


Basic Information

Motivation The past decade has seen a lot of applications of Algorithmic techniques related to Algebraic structures in various sub-areas of theoretical computer science. In particular, areas like Algorithms, Computational Geometry, Cryptography and Complexity Theory have benefited immensely from these algorithmic techniques. This course aims to introduce these algorithms and some of their applications in a systematic manner. We will be particularly focusing on algorithmic problems and techniques related to polynomials.
Syllabus :
Introduction : Motivation to study algorithmic problems related to polynomials - overview of example applications. The language - Rings, Fields, Ideals, and Polynomials.
Algorithms for Polynomials . Algorithm for GCD: Euclid’s algorithm. Hilbert’s basis theorem. Solving polynomial equations; ideal membership problem; Grӧbner 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.

Pre-requisites

Any student who is interested in algebra and computation and having basic discrete mathematics training. We will have a quick crash course on (indeed, some of them may be left as small reading assignments) the basic algebraic structures needed and get to the "algorithmic part". But the course is intended to be "more-or-less" self-contained. The course is intended to be reaching out students who would wish to see algorithmic ideas borrowed from and applied to rich algebraic structures.

Evaluation Scheme

Course evaluation will be based on three exams and a set of problem sheets (theoretical) given at regular interval. The weights of each of the activities is as under:
  • Problem Sets: 35%
  • Quiz-1 15%
  • Quiz-2 15%
  • End Semester Exam 35%