Efficient computation of generators of special invariant rings

Project Description

Since Hilbert’s seminal works on invariant theory, which laid foundational results for modern commutative algebra and algebraic geometry, and Mumford’s seminal work on geometric invariant theory, much progress has been made on the computational aspects of invariant theory. Despite all of the progress made in this past century, many open questions still remain on the efficient computation of a generating set (or of a separating set) of invariant polynomials. The goal of this project is to make progress in efficiently computing a generating set of invariant polynomials for special group actions, which have profound applications in fundamental theoretical problems in computer science.

Background Reading

Some useful references for this project are:

• Chapters 1 and 2 of Bernd Sturmfels’ book Algorithms in Invariant Theory
• Derksen & Kemper Computational Invariant Theory
• Garsia & Stanton Group actions on Stanley-Reisner rings and invariants of permutation groups
• Babai’s graph isomorphism course
• Babai’s graph isomorphism survey
• Understanding of Weisfeiler-Lehman algorithm and other graph isomorphism algorithms. A tutorial on the Weisfeiler-Lehman algorithm can be found here. And more can be found here and here.
• Ramprasad’s course on Computational Group Theory and Computational Algebra
• Eugene Luks’ 1990 Lectures on Polynomial Time Computation in Groups
• Seress’ book Permutation Group Algorithms, PDF available through the UW library
• Richard Borcherds’ commutative algebra lectures
• Richard Borcherds’ algebraic geometry lectures

Prerequisites

The ideal URA should have a solid command of:

• linear algebra (equivalent of MATH 245, or MATH 235),
• basic abstract algebra (such as the material from both PMATH 336 and PMATH 347),
• commutative algebra,
• some programming experience being a plus.

Programming will be done using Macaulay 2 (no prior experience with this language required).

Note: some of the prerequisites can be waived if the student has excellent academic background, such as international olympiads experience, or other similar achievements.

Applying

If you are interested and have the prerequisites for this project, please send me the following by email:

• Transcript
• Resume
• 1-2 paragraphs on why you are interested in this project (in particular, you should understand at least what the Weissfeiler-Lehman algorithm is)

Note: any applications deviating significantly from the above instructions will be ignored.