Instructor: Nikhil Balaji (nbalaji)
Slot: AB (Mon, Thu - 15:30 - 17:00)
Venue: TBD
Groups, Rings, Fields and algorithms to manipulate them with applications.
Algorithms for integer and polynomial multiplication.
Primality testing and Integer factorisation
Irreducibility testing and Polynomial factorisation (univariate, multivariate, over finite fields, rationals) algorithms
Algorithms for solving polynomial systems, quantifier elimination over various fields.
Polynomial Identity Testing and applications.
Algebraic models of computation: BSS model, Valiant's model, Algebraic Decision Trees, Algebraic P vs NP.
COL351, COL352, COL705 OR Equivalent. Essentially, a working knowledge of Discrete Mathematics (Linear Algebra, Combinatorics, Discrete Probability) and Design and Analysis of Algorithms and/or Theory of Computation. If you haven't done the prerequisite courses, but are interested in attending, please send me an email.
Problem sets/quizzes -- 50% (approx), Major exam/Viva -- 25% (approx), Final Project -- 25% (approx).
Depending on the class strength (the number of students crediting the course), students will be put into groups of size at most 2 and given topics to read/present/work on open problems. Every group will be expected to give a clear presentation (30-60 minutes) and will be expected to generate an electronic report (approx 10 pages long using LaTeX).
TBD
[Shoup]: A Computational Introduction to Number Theory and Algebra by Victor Shoup
[vzGG]: Modern Computer Algebra by von zur Gathen and Gerhard
[Sudan]: Course on Algebra and Computation by Madhu Sudan
[Saxena]: Course on Arithmetic Circuit Complexity by Nitin Saxena