CMPT 409 & 981: Algebra and Computation
Course project guidelines
The goal of the course project is for you to
- learn something new and interesting about algebra and computation,
- gain experience reading research papers, and
- practice communicating technical ideas in both spoken and written form.
In groups of at most three, you will select and read a research paper related to the topics of this course, present the results of this paper to your peers, and write a short report on what you learned.
Collaboration is strongly encouraged: Reading and understanding a research paper is much easier (and more fun!) if you have someone to talk to as you read.
If you need help finding a project group, you can use the discussion forum on CourSys to reach out to your classmates.
Alternatively, you are welcome to work on original research as long as it is related to the content of the course in some way.
Project proposal
Due October 28, 11:59pm, on Crowdmark.
Submit the names of your group members and the paper that you plan to read or the problem(s) you intend to work on.
Only one member of the group needs to submit this.
It’s fine if you want to change your paper selection later on, but I encourage you to discuss it briefly with me before doing so.
Project report
Due December 7, 11:59pm, on Crowdmark.
Write a report describing the paper you read.
This should be roughly 10 pages (11pt font, 1 inch margin, single column, single spaced) if working alone, 15 pages if working in a group of two, and 20 pages if working in a group of three.
Your report does not have to be exhaustive, so what should you write about?
Imagine you had an hour or two at the whiteboard to tell one of your classmates about the paper.
How would you introduce the paper and the problem it studies?
What technical content would you tell them, and what would you skip for time’s sake?
What interesting questions remain?
Your report should be a written version of whatever you might tell your classmate about.
As a rough guideline, your report should include:
- An introduction to the problem studied in the paper: what is the context? Why is the problem important or interesting?
- A description, in your own words, of what new advances are made in the paper and (some of) the new technical content.
- If applicable, a comparison to any of the material we’ve seen so far in class.
- Further questions or directions for research left open by the paper. If you have half-baked ideas you have on how to improve/apply/generalize/simplify the paper, include them!
Project presentation
Presentations will take place during the exam period in December. Exact date and time TBD.
Present the paper you read to the rest of the class.
Your presentation should be 15-20 minutes long if working alone, 20-25 minutes if working in a group of two, and 25-30 minutes if working in a group of three.
This will be similar to a paper presentation at a conference.
As in your report, you should describe the background and context for the paper: what problem does the paper study, what results were previously known, and what are the new results.
Then tell us about some of the technical ideas in the paper.
You will not have time to cover all the details, so choose the ones you find most interesting or insightful.
If there are connections to problems or topics we have seen in class, tell us.
Finish by describing problems left open by the paper or interesting directions for future research.
Papers and where to find them
Computer algebra and algebraic complexity theory are active areas of research.
You can find papers in the proceedings of major conferences such as STOC, FOCS, CCC, SODA, ITCS, and ISSAC, journals such as Journal of the ACM, SIAM Journal on Computing, computational complexity, Theory of Computing, Journal of Symbolic Computation, or preprint servers such as arXiv and ECCC.
You can also browse by author at DBLP or visit an author’s homepage.
There is a list of example papers below.
You are not required to choose a paper from this list.
Feel free to come to office hours (or make an appointment) if you want advice on choosing a paper to read.
Some tips
- Don’t be afraid to explore the citation graph in both directions.
Google Scholar can help find papers that cite a given paper.
- Some papers have multiple versions (preprint, conference, journal). In general, the journal version is the most polished, if it exists. Conference versions are sometimes subject to page limits, with details only appearing in a full version on arXiv or ECCC.
Example papers
Algorithms
- Fast solution of Toeplitz systems of equations and computation of Padé approximants by Brent, Gustavson, and Yun (J. Algorithms ‘80)
- Fast computation of special resultants by Bostan, Flajolet, Salvy, and Schost (J. Symb. Comput. ‘06)
- Fast Integer Multiplication Using Modular Arithmetic by De, Kurur, Saha, and Saptharishi (SICOMP ‘13)
- Fast Multivariate Multipoint Evaluation over All Finite Fields by Bhargava, Ghosh, Guo, Kumar, and Umans (J. ACM ‘24)
- Power Series Composition in Near-Linear Time by Kinoshita and Li (FOCS ‘24)
- Kronecker Products, Low-Depth Circuits, and Matrix Rigidity by Alman (SICOMP ‘26)
- Fast Polynomial Factorization and Modular Composition by Kedlaya and Umans (SICOMP ‘11)
- Parameterized Applications of Symoblic Differentiation of (Totally) Multilinear Polynomials by Brand and Pratt (ICALP ‘21)
- The shortest even cycle problem is tractable by Björklund, Husfeldt, and Kaski (STOC ‘22)
- Polynomial decomposition algorithms by Kozen and Landau (J. Symb. Comput. ‘89)
- A Group-theoretic Approach to Fast Matrix Multiplication by Cohn and Umans (FOCS ‘03) and Group-theoretic Algorithms for Matrix Multiplication by Cohn, Kleinberg, Szegedy, and Umans (FOCS ‘05)
- Fast Parallel Computation of Polynomials Using Few Processors by Valiant, Skyum, Berkowitz, and Rackhoff (SICOMP ‘83)
- Towards Optimal Depth-Reductions for Algebraic Formulas by Fournier, Limaye, Malod, Srinivasan, and Tavenas (comput. complex. 2026)
- Representations and Parallel Computations for Rational Functions by von zur Gathen (SICOMP ‘86)
- Very Fast Parallel Polynomial Arithmetic by Eberly (SICOMP ‘89)
- Computing Algebraic Formulas Using a Constant Number of Registers by Ben-Or and Cleve (SICOMP ‘92)
- Constant-Depth Arithmetic Circuits for Linear Algebra Problems by myself and Wigderson (FOCS ‘24)
- On the Complexity of Numerical Analysis by Allender, Bürgisser, Kjeldgaard-Pedersen, and Miltersen (SICOMP ‘09)
- Hilbert’s Nullstellensatz is in the Polynomial Hierarchy by Koiran (J. Complex. ‘96)
Complexity theory
- Arithmetic Circuits: A Chasm at Depth 3 by Gupta, Kamath, Kayal, and Saptharishi (SICOMP ‘16)
- On the Complexity of Symmetric Polynomials by Bläser and Jindal (ITCS ‘19)
- A Lower Bound for the Formula Size of Rational Functions by Kalorkoti (SICOMP ‘85)
- Lower bounds for non-commutative computation by Nisan (STOC ‘91)
- Multi-linear formulas for permanent and determinant are of super-polynomial size by Raz (J. ACM ‘09)
- Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits by Limaye, Srinivasan, and Tavenas (J. ACM ‘25)
- Low-Depth Algebraic Circuit Lower Bounds over Any Field by Forbes (CCC ‘24)
- Characterizing Valiant’s algebraic complexity classes by Malod and Portier (J. Complex. ‘08)
- Cook’s versus Valiant’s hypothesis by Bürgisser (Theor. Comput. Sci. ‘00)
- Deterministic polynomial identity testing in non-commutative models by Raz and Shpilka (comput complex. ‘05)
- Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs by Forbes and Shpilka (STOC ‘13)
- Derandomization from Algebraic Hardness by Guo, Kumar, Saptharishi, and Solomon (SICOMP ‘22)
- Hitting Sets for Polynomials with Small Partial Derivative Spaces by Bharadwaj and Saptharishi (2026)
- Dimension Expanders via Rank Condensers by Forbes and Guruswami (RANDOM ‘15)
- Randomness Efficient Identity Testing of Multivariate Polynomials by Klivans and Spielman (STOC ‘01)
- Equivalence of Polynomial Identity Testing and Polynomial Factorization by Kopparty, Saraf, and Shpilka (comput. complex. ‘15)
- Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Prof System by Grochow and Pitassi (J. ACM ‘18)
- Proof Complexity Lower Bounds from Algebraic Circuit Complexity by Forbes, Shpilka, Tzameret, and Wigderson (Theory Comput. ‘21)