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.
SyllabusAlgorithms 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 and Pre-requisiteAny 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.
Evaluation:Problem Sets (4x10 = 40%)
Mid sem exam (20%)
End Sem exam (25%)