Basic Information

Note: Submissions/evaluations will be managed on Gradescope portal.

What is this course about?

The past few decades have seen a lot of applications of Algorithmic techniques related to Algebraic structures in various sub-areas of theoretical computer science. In particular, areas like Algorithms, Computational Geometry, Cryptography and Complexity Theory have benefited immensely from these algorithmic techniques. This course aims to introduce these algorithms and some of their applications in a systematic manner. We will be particularly focusing on algorithmic problems and techniques related to rings and polynomials.

Learning outcomes

• To abstract out and apply techniques related to algebraic objects in various aspects of computer science.
• To relate to algorithmic research challenges in algebraic objects. Be aware of the fundamental research questions in these directions.

Syllabus?

• Algorithms for Polynomials & Applications : Algorithm for GCD: Euclid’s algorithm. Hilbert’s basis theorem. Solving polynomial equations; ideal membership problem; Grobner bases: Buchberger’s algorithm. Representation, Factorization Problem. Polynomial Identity Testing problem; Applications to Primality Testing: AKS Primality test; Complexity of Polynomials. Polynomial and Matrix Multiplication Problems, Permanent vs Determinant problem and connections to Polynomial Identity Testing.

Target audience? Pre-requisites?

Any student who is interested in algebra and computation and having basic discrete mathematics training. We will be quickly covering the basic algebra needed and get to the "algorithmic part". But the course is intended to be self-contained. The course is intended to be reaching out students who would wish to see algorithmic ideas borrowed from and applied to rich algebraic structures.

On a first look at the name and the contents, this course might look a bit difficult because of many reasons - 1) the term "algebra" in the name sends people off, 2) the term "complexity" in the syllabus sends people off. If you are worried about pre-requisites, read the section above. And, if you managed to convince yourself to take this course, congratulations - you seem to be on the right track! :-).

Classroom mode

Traditional Lectures. 4 lectures of 50 minutes each at Tue @11am, Wed @ 10am, Thu @8am, Fri @2:30pm all at CSB 36. There will be separate slots for midsem exam, problem set discussions, etc.

Textbooks

• 'An Introduction to Grobner Bases' by William Wells Adams, Philippe Loustanau.
• 'Modern Computer Algebra' by Jurgen Gerhard, Joachim von zur Gathen.
• 'Ideals, Varieties, Algorithms' by Cox, Little, O'Shea.
• 'Algebraic Complexity Theory' by Burguisser, Clausen, Shrokhollahi.

Course requirements

You are required to attend all the lectures. If you miss any of them it is your responsibility to find out what went on during the classes and to collect any materials that may be handed out. Class participation is strongly encouraged to demonstrate an appropriate level of understanding of the material being discussed in the class. Regular feedback from the class regarding the lectures will be very much appreciated.

Activities and tentative Grading policy:

• Problem Sets (8% x 5 = 40%): Following are the submission deadlines for the problem sets. The problems sets will be posted in an incremental fashion. That is, the dropbox file will be updated after the class covers the relevant lectures. It is expected that the problem set questions are worked on as and when they are released so that the lecture material is also practiced/applied right away. Note: All deadlines are set to Sundays 10pm. The last problem in a problem set will be added at least about a week before its submission deadline. Problem Set 1 : Feb 15, 2026. Problem Set 2 : March 01, 2026. Problem Set 3 : March 29, 2026. Problem Set 4 : April 12, 2026. Problem Set 5 : April 26, 2026.
• Course Presentation (20%): The course presentation is designed to encourage you to read and explore on your own a material that is closely related to the ideas done in class. One small topic (possibly from a lecture notes or research paper or textbook) will be assigned to each of you, Each of you is expected to get on stage to talk about the topic in full technical detail for about 45 minutes. These presentations will be scheduled on March 14-15 and May 2-3 (tentatively) respectively.
• Exams + Viva: Exam 1 (20%) : March 14, 2026 (tentative). Exam 2 (20%) : May 12, 2026.
The course will follow a relative absolute grading (RAG) scheme, wherein wherein rough (i.e., a small interval for) cut-off for each grade will be fixed apriori, but the exact cut-off will be decided post-evaluation based on class average and the gaps in marks; it'll be done in a manner that ensures that nobody misses a higher grade by ≤ 2 marks. The cut-off ranges are as follows: 85-90 (S), 75-80 (A), 65-70 (B), 55-60 (C), 45-50 (D), 35-40 (E).