Topics in Algebra and Computation
General information
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
Lectures: Tue/Fri 5:30 pm to 6:55 pm
Office hours: Tue/Fri 6:55 pm to 7:30 pm
Logistics
The course will be taught online, with lectures on google meet, and online office hours. If you have logistic constraints that make any of this difficult, please send me an email, and we can try to figure a way around this. We will use Moodle for announcements and discussions.
Grading
Grades will be based on some problem sets and a course project. The details of the course project will be up on Moodle soon, but very roughly, it will involve reading some papers, writing a short summary of those and giving a short talk.
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.
Homeworks
- Homework 1 due on Aug 20.
- Homework 2 due on Sep 13.
- Homework 3 due on Oct 05.
- Homework 4 due on Oct 29.
- Additional problems (Not to be submitted).
Schedule
-
July 27 (Lec 0): Admin things: tentative content, grading etc.
-
July 30 (Lec 1): Basic algebra background - intro to fields, commutative rings, integral domains, UFDs.
-
Aug 03 (Lec 2): Ring of polynomials, division lemma, GCD and properties.
-
Aug 06 (Lec 3): Structure of field extensions, coefficients vs evaluations for univariate polynomials.
-
Aug 10 (Lec 4): Fast polynomial multiplication.
-
Aug 13 (Lec 5): Fast polynomial division with remainder.
-
Aug 17 (Lec 6): Univariate multipoint evaluation, GCD computation.
-
Aug 20 (Lec 7): Chinese remainder theorem, Resultants.
-
Aug 24 (Lec 8): Resultants contd., discriminant and square freeness, Gauss' Lemma.
-
Aug 27 (Lec 9): Fast multivariate multipoint evaluation over finite fields.
-
Aug 31 (Lec 10): Lower bound for data structures for polynomial evaluation.
-
Sep 03 (Lec 11): Upper bound for data structures for polynomial evaluation.
-
Sep 07 (Lec 12): Algorithm for computing square roots over finite fields.
-
Sep 10: Institute holiday..no class.
-
Sep 14: Mid-sem week..no class.
-
Sep 17: Mid-sem week..no class.
-
Sep 21 (Lec 13): Cantor and Zassenhaus' algorithm for univariate factorization over finite fields.
-
Sep 24 (Lec 14): Berlekamp's algorithm for univariate factorization over finite fields.
-
Sep 28 (Lec 15): Factoring bivariate polynomials.
-
Oct 1 (Lec 16): Factoring bivariate polynomials contd.
-
Oct 5 (Lec 17): Arithmetic circuits intro - homogenization, division elimination.
-
Oct 8 (Lec 18): Efficient parallel computation of determinant, application to bipartite matching.
-
Oct 12 (Lec 19): Multivariate factorization - Kaltofen's algorithm.
-
Oct 15 (Lec 20): Multivariate factorization - Kaltofen's algorithm contd.
-
Oct 19 (Lec 21): An application of Kaltofen's algorithm- PIT from algebraic hardness.
-
Oct 22 (Lec 22): Certificate for primality, Agrawal-Biswas primality test.
-
Oct 26 (Lec 23): AKS primality test.
-
Oct 29 (Lec 24): AKS primality test contd.
-
Nov 2 : Student presentations.
-
Nov 5 : Student presentations.
References