Basic Information


What is this course about?

The past few decades have 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 groups, rings and polynomials.

Syllabus?

  • Algorithms for Groups & Applications : Basic group theory. Graph Isomorphism (GI) Problem, Automorphism Group, Permutation Groups. Generators, Schreier-Sims algorithm. Orbit and Stabilizer. Membership Testing in permutation Groups. Jerrum's Filter, Group Intersection Problem. Algorithms for bounded degree graph isomorphism, bounded eigen value multiplicity Graph Isomorphism.
  • Algorithms for Polynomials & Applications : Representation, Factorization Problem. Polynomial Identity Testing problem; Applications to Primality Testing: AKS Primality test; Complexity of Polynomials. Polynomial and Matrix Multiplication Problems, Permanent vs Determinant problem and connections to Polynomial Identity Testing.

Target audience? Pre-requisites?

Any student who is interested in algebra and computation and having basic discrete mathematics training. We will be quickly covering the basic algebra needed and get to the "algorithmic part". But the course is intended to be 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.

On a first look at the name and the contents, this course might look a bit difficult because of many reasons - 1) the term "algebra" in the name sends people off, 2) the term "complexity" in the syllabus sends people off. If you are worried about pre-requisites, read the section above. And, if you managed to convince yourself to take this course, congratulations - you seem to be on the right track! :-).

Evaluation:

The course grading will be done in "absolute" scale rather than "relative" scale. That is, Grades will depend on four parameters listed in activities page with the following weightage.

  • Problem Sets (4x7 = 28%)
  • Lecture Scribing (7%)
  • Exam-1 (20%)
  • Exam-2 (30%)
  • Presentation (15%)

For an 'S' grade one needs to score at least 90 in the over-all evaluation. The cut offs for 'A' will be 80, 'B' will be 70, 'C' will be 60, 'D' will be 50, 'E' will be 40 and below 40 is the fail grade.