COL 863 : Algebra and Computation (Topics in TCS)

Staff

Instructor: Nikhil Balaji (nbalaji)

Slot: AB (Mon, Thu - 15:30 - 17:00)

Venue: TBD

What is this course about?

Algebra is a central tool in both designing algorithms (think fast integer multiplication, matrix multiplication, etc.) and understanding the limitations of computation itself (algebraic complexity theory). This course will touch upon both these topics.

Topics (tentative)

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.

Prerequisites

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.

Course Logistics and Grading (Tentative)

Problem sets/quizzes -- 50% (approx), Major exam/Viva -- 25% (approx), Final Project -- 25% (approx).

Project Topics

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).

Schedule

TBD

References

[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