CS 487/687 Final Project

For the final project, you will be asked to work on an open problem in Algebraic Computation or Symbolic Computation and present a survey about the problem and the outcomes of your investigations at the end of the term, or to present a survey of a topic of your choice (see some example topics below).

A coding project is also an option for the final project. In the coding project you will be asked to write code for a problem where the current algorithms have not yet been implemented. Most likely the coding project will be done with the language Macaulay 2. If you would like to do a coding project, please email me so we can discuss appropriate problems.

The ideal project would be a problem/topic that you are excited about - this often brings one the most joy. If you need some guidance in picking a problem to present on, I will be happy to meet with you to hone into a problem of your liking.

The topics below are simply a suggestion. If you have another topic of your interest which is not covered here, I will be happy to try and work out with you a possible project on your topic of choice.

Undergraduate students can do their final project in pairs, but it is not mandatory. I will leave it to you to coordinate the pairing for the final project.

Timeline for the final project

• February 12th: project teams due
• March 8th: project proposals due
• April 18th: project reports due
• April 19th-23rd: project presentations due

Template for final project

For the final project, we strongly recommend you to write your report in LaTeX. A template that you can edit accordingly is given here.

Project Presentations

The final project presentation will have a duration of 30 minutes per student. Each student is required to prepare and present individually. The timeline of the presentation is as follows: you will have 20 minutes to present what you did in your project and then we will have a 10 minutes of Q&A between you and me.

In the 20 minutes that you have to present, I expect you to prepare slides (whichever way you want to) to present to me the following:

• What is the problem that you are studying
• Why is the problem important (background, history, etc)
• What is your main contribution (for instance, for survey projects, you will have to explain to me how the algorithm works - to a reasonable degree, no need to go too much in detail - I may ask questions later in the Q&A part)
• Conclusion

To sign up to the time slots, please see the link posted on Piazza.

Research-based projects

I highly encourage you all to try your hands at an open problem! It is an amazing and enriching experience, and you may end up solving it by the end of the class!

For those of you who want to use this opportunity to start working on some research problems (perhaps as a pre URA or an URA), here are people that you can check out their webpages/try to reach out to, or resources at your disposal, for you to look for suitable projects:

• Algorithms and Complexity faculty webpage
• Symbolic Computation faculty webpage
• UW URA webpage

A good strategy to find interesting open problems is to look at a particular faculty’s advanced graduate course’s webpage and see the topics they are interested in and the open problems in the area that they would be interested in. You can use your final project to get a deeper understanding in such an area where your interests match.

Possible Topics for Final Project

• Analysis of Algebraic Algorithms for Graph Isomorphism Problem
• Algorithms in Computational Group Theory
• Algebraic Algorithms in Invariant Theory
• Algorithms in Algebra and Algebraic Geometry Ideals, Varieties and Algorithms and Using Algebraic Geometry
• Computational Algebraic Geometry Hal Schenck’s book
• Hal Schenck’s Algebra and Topology for Data Analysis
• Kedlaya-Umans Fast Polynomial Factorization and Modular Composition
• Fleming, Kothari, Pitassi Semialgebraic proof systems & algorithms survey
• Mayr & Meyer paper on complexity of ideal membership problem
• Algorithms for Coding Theory (error correcting codes, list decoding, compression, locally decodable/correctable codes, codes that handle deletions, etc)
• Algorithms for Number Theory (last I checked we still could not factor integers quickly :) ) a reference on number theoretic algorithms by Shoup
• Algebraic Algorithms in Cryptography: lecture notes by Pass and Shelat
• Applications of the Short Vector in a Lattice problem: breaking certain cryptosystems, finding simultaneous Diophantine approximations, refutation of Mertens’ conjecture. See [vzGG] book, chapter 17, for this part.
• Sparsity of factors of sparse polynomials: see recent result of BSV'18
• Multivariate poylnomial factoring algorithm. See Madhu’s notes
• Kaltofen’s favourite open problems in Symbolic Computation PDF