Workshop
The Complexity of Polynomial Subalgebras and their Initial Algebras
- Leonie Kayser (MPI MiS)
Abstract
The computational complexity of polynomial ideals and Gröbner bases has been studied since the 1980’s.
In recent years the related notions of polynomial subalgebras and SAGBI bases have gained more and more attention in computational algebra, with a view towards effective algorithms.
In this talk we investigate the computational complexity of the membership problem for subalgebras and give degree bounds.
We also present a conjectural structure theory for their (often infinitely generated) initial algebras.
We highlight the parallels and differences compared to the "ideal world" and also look at important classes of polynomials such as homogeneous and monomial algebras.
Based on joint work with Bernhard Reinke.
