Topics in Computational Ring Theory and Algebras
General information
Course Number : CS 711
(Unofficial) Title : Topics in Algebra and Computation
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
Logistics
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.
Grading
Grades will be based on problem sets and a course project. The details of the course project will be up on Moodle soon.
Prerequisites
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.
Description
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.
Lectures
-
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: Arithmetic circuits - homogenization, division elimination. Determinant in VNC2.
-
Oct 05-09: No class (Midterm week).
-
Oct 12-16: Multivariate Factorization - Kaltofen's theorem.
-
Oct 19-23: Hilbert's Irreducibility Theorem. Bezout's theorem.
-
Oct 26-30: Ideals and Varieties, Ideal Membership problem, Groebner basis, Hilbert's basis theorem.
-
Nov 02-06: Groebner basis contd. - Buchberger's criterion. Degree bound for Ideal Membership.
-
Nov 09-13: Elimination Ideals, Hilbert's Nullstellansatz.
-
Nov 16-20: Hilbert's Nullstellansatz contd. Algebraic independence and Jacobian criterion.
References