Projects per year
Abstract
Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. Sénizergues and the fifth author (ICALP2018) proved that the isomorphism problem for virtually free groups is decidable in PSPACE when the input is given in terms of socalled virtually free presentations. Here we consider the isomorphism problem for the class of plain groups, that is, groups that are isomorphic to a free product of finitely many finite groups and finitely many copies of the infinite cyclic group. Every plain group is naturally and efficiently presented via an inverseclosed finite convergent lengthreducing rewriting system. We prove that the isomorphism problem for plain groups given in this form lies in the polynomial time hierarchy, more precisely, in Σ^{P}_{3}. This result is achieved by combining new geometric and algebraic characterisations of groups presented by inverseclosed finite convergent lengthreducing rewriting systems developed in recent work of the second and third authors (2021) with classical finite group isomorphism results of Babai and Szemerédi (1984).
Original language  English 

Title of host publication  39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022 
Editors  Petra Berenbrink, Benjamin Monmege 
Place of Publication  Germany 
Publisher  Schloss Dagstuhl 
Number of pages  14 
ISBN (Print)  9783959772228 
DOIs  
Publication status  Published  1 Mar 2022 
Event  International Symposium on Theoretical Aspects of Computer Science 2022  Virtual Conference Duration: 15 Mar 2022 → 18 Mar 2022 Conference number: 39th https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16222 (Proceedings) https://stacs2022.sciencesconf.org/#:~:text=The%2039th%20International%20Symposium%20on,site%20presence%20component%20in%20Marseille. 
Publication series
Name  Leibniz International Proceedings in Informatics, LIPIcs 

Volume  219 
ISSN (Print)  18688969 
Conference
Conference  International Symposium on Theoretical Aspects of Computer Science 2022 

Abbreviated title  STACS 2022 
Period  15/03/22 → 18/03/22 
Internet address 
Keywords
 Inverseclosed finite convergent lengthreducing rewriting system
 Isomorphism problem
 Plain group
 Polynomial hierarchy
 Σ complexity class
Projects
 1 Finished

Computing with Lie groups and algebras: nilpotent orbits and applications
Dietrich, H. & de Graaf, W. A.
1/04/19 → 31/01/23
Project: Research