Dehn's problems in Computational Group Theory

Abstract: In 1911, Max Dehn introduced three decision problems: the word, conjugacy, and isomorphism problems. These three soon turned into cornerstones of geometric group theory and, moreover, the conjugacy and isomorphism problem became highly influential across many areas of computational group theory. Concretely, the conjugacy problem considers two elements $g,h$ and a group $G$; it asks if there exists $x \in G$ with $x^{-1} g x = h$. The isomorphism problem asks if two groups $G$ and $H$ are isomorphic.

This talk offers an introduction to the main areas of computational group theory and surveys the algorithms used to solve the conjugacy and isomorphism problems in various settings. Canonical forms are a key tool for both problems. The talk includes pointers to their construction and explains their applications.

Complete Reductions for Symbolic Integration

Abstract: Finding indefinite integrals in finite terms is a classical topic in computer algebra. A key problem is the recognition of derivatives -- deciding whether an element of a differential field is a derivative and computing an antiderivative within the field when one exists.

A complete reduction constructs a complement to the subspace of derivatives, allowing any field element to be algorithmically decomposed into the sum of a derivative and an element lying in the complement. Such a decomposition recognizes derivatives immediately. The first complete reduction was introduced for rational integration by Ostrogradsky and Hermite in the nineteenth century, while recent developments are strongly motivated by reduction-based creative telescoping.

This tutorial describes a complete reduction in the setting of transcendental Liouvillian extensions, which include transcendental elementary extensions as a special case.

The reduction provides an alternative to the Risch algorithm for computing elementary integrals.

Designing and exploiting fast algorithms for polynomial matrices

Abstract: Matrices whose entries are univariate polynomials over a field are a basic mathematical object that plays an important role in some fundamental algorithms in computer algebra. This includes solving sparse or structured linear systems, finding low-degree vectors in polynomial modules, guessing algebraic relations via Hermite-Padé approximants, or computing bivariate resultants or lexicographic Gröbner bases for multivariate ideals. In this tutorial, we will start with a gentle introduction to polynomial matrices and basic operations on them. Then, we will give an overview of the main algorithmic ideas that have been developed during the last few decades in the search for fast polynomial matrix methods, and we will discuss software implementation aspects. Finally, we will conclude with a focus on the use of polynomial matrices to accelerate the modular composition of univariate polynomials and the multipoint evaluation of bivariate polynomials.