Algorithmic Problems in Group Theory

• Applicants: Professor Dr. Markus Lohrey; Dr. Armin Weiß
• Subject Area: Theoretical Computer Science
• Term: from 2016 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 288360912

The main objectives outlined in the first proposal also apply to this new proposal:- Pinpointing the complexity of algorithmic problems in group theory (in particular word problems and conjugacy problems) in terms of small complexity classes from circuit complexity and space complexity. Here we made significant progress in the last 4 years.- From a broader perspective we want to promote the field of algorithmic group theory in Germany. First promising steps were already made.The focus for the first point moved slightly: While in our first proposal the emphasis was primarily on graph products and fundamental groups of graphs of groups (with generalized Baumslag-Solitar groups as an important special case), we plan for the next three years to widen this spectrum to other important classes such as automaton groups and metabelian groups. Furthermore, we want to extend our investigations also to computational problems that are located on higher levels of the complexity spectrum: discrete optimization problems, word equations, and compressed word problems. In the first project phase we have developed new techniques in order to tackle these problems. We plan to further investigate the applicability of these techniques.

• DFG Programme: Research Grants