Algebra and Computation
Course Number : CS 711
(Official) Title : Topics in Computational Ring Theory and Algebras
Instructor : Mrinal Kumar
Email : first name AT cse DOT iitb DOT ac DOT in
Official class timing : Tue/Fri 5:30 pm to 6:55 pm
(Online) Office hours : Tue/Fri 5:30 pm to 6:55 pm
The course will be taught online, with a combination of recorded video lectures and notes, and office hours every week online (and on phone if needed). If you have logistic constraints which make this difficult, please send me an email, and we can try to figure a way around this.
Grades will be based on problem sets and a course project. The details of the course project will be up on Moodle soon.
Mathematical maturity, familiarity with the contents of a typical undergrad Discrete Math and Algorithms Class.
This is a theory course, so you should be comfortable around mathematical statements and proofs. You are NOT expected to have a background in advanced algebra for this class and the course will be self contained for the most part. The course is open to third and later year undegrads and masters and PhD students. If you aren't from one of these sets and would like to attend, feel free to drop me an email.
As the name suggests, the course will focus on the relationship between algebra and computation. A large part of the course will focus on computational problems in algebra. Towards the end, we will also discuss some upper and lower bounds in algebraic complexity theory.
A tentative list of topics can be found here.
Aug 12-14: Admin things: tentative content, grading etc
Aug 17-21: Basic algebra background - Intro to Fields, Commutative Rings, UFDs, Polynomial Rings.
Aug 24-28: Computation with univariate polynomials - FFT, fast polynomial multiplication, division with remainder.
Aug 31-Sep 4: Univariate multipoint evaluation, GCD computation, Resultants, Gauss' Lemma.
Sep 07-11: Univariate factorization over finite fields - randomized algorithm of Cantor and Zassenhaus.
Sep 14-18: Univariate factorization contd. - Berlekemp's algorithm. Finite fields: existence and uniqueness. SZ-Lemma.
Sep 21-25: Bivariate Factorization via Newton Iteration.
Sep 28-Oct 2: No class (Midterm week).
Oct 05-09: Arithmetic circuits - homogenization, division elimination. Determinant in VNC2.
Oct 12-16: Multivariate Factorization, Hilbert's Irreducibility Theorem. Bezout's theorem.