CMPT 409 & 981: Algebra and Computation

Instructor: Robert Andrews (robert_andrews@sfu.ca)

TA: Hazel Guan

Lectures: Wednesday 3:30–4:20pm and Friday 2:30–4:20pm, AQ 4120

Office hours: Thursday 3:00–4:00pm (or by appointment), TASC1 9405

Discussion forum: CourSys

Course overview

Course description

This course will cover a variety of topics that lie in the intersection of algebra, algorithms, and complexity theory. The contents of this course are divided into three parts.

1. In the first part of the course, we will cover basic algorithms for computing with polynomials and matrices, learning tools and techniques useful for the design of algorithms for algebraic problems.
2. The second part will introduce complexity-theoretic aspects of algebra and computation through arithmetic circuit complexity and the polynomial identity testing problem.
3. The final part of the course will cover powerful and surprising applications of algebra to other areas of theoretical computer science, many of which occurred in the last few years!

Prerequisites

Mathematical maturity and strong background in undergraduate-level algorithms, linear algebra, and probability theory. Prior background with advanced algebra will be useful, but is not necessary; the course will largely be self-contained.

Coursework

• Five homework assignments, worth 40%
  • We will use Crowdmark to manage homework assignments. You may need to access Crowdmark through Canvas.
  • Homework will be released after lecture on Wednesdays and will be due at the start of lecture two weeks later. When this falls on a campus holiday, release dates will be moved earlier and due dates moved later.
• Course project, worth 60%
  • In groups of 2 or 3, you will select and read a research paper related to the topics of this course, present this paper to your peers, and write a short report on what you learned.
  • A suggested list of papers will be posted later in the term.

Collaboration policy

You may work on and discuss homework problems with one another. However, each student must individually write their own solutions and list any collaborations in which they participated. If you use external sources, be sure to cite them. Be mindful of the course policy on generative AI below.

Late work policy

Any assignment may be submitted up to two days (i.e., 48 hours) late, no questions asked. Late assignments will receive a 10% grade penalty.

Generative AI use

Generative AI has had an astounding impact on research in mathematics and theoretical computer science. These tools are poised to be widely adopted, and it is important to learn to use them effectively.

However, the goal of this course is for students to learn the course content and be exposed to a beautiful connection between mathematics and computer science. This kind of learning requires time, effort, and active engagement. To this end, the use of generative AI to complete work in this course is prohibited.

Course schedule

This is a tentative schedule of the topics we plan to cover during the course and is subject to change.

Other resources

Similar courses taught by others

• Algebra, Number Theory, and Computation by Mrinal Kumar at TIFR (2026)
• Algebra and Computation by Madhu Sudan at MIT (2015)
• Algorithms in Algebra and Number Theory by Swastik Kopparty at Toronto (2021)
• Commutative Algebra with a view Towards Complexity Theory by Rafael Oliveira at Waterloo (2025)
• Algebraic Complexity Theory by Rafael Oliveira at Waterloo (2024)
• Algebraic Circuit Complexity by Ramprasad Saptharishi at TIFR (2024)

Textbooks and supplementary reading