Dagstuhl Seminar 19131
Algorithmic Problems in Group Theory
( Mar 24 – Mar 29, 2019 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/19131
Organizers
- Volker Diekert (Universität Stuttgart, DE)
- Olga Kharlampovic (The City University of New York, US)
- Markus Lohrey (Universität Siegen, DE)
- Alexei Myasnikov (Stevens Institute of Technology - Hoboken, US)
Contact
- Michael Gerke (for scientific matters)
- Annette Beyer (for administrative matters)
Impacts
- Complexity and Randomness in Group Theory - Bassino, Frederique; Kapovich, Ilya; Nikolaev, Andrey; Rivin, Igor; Shpilrain, Vladimir; Weil, Pascal; Ushakov, Alexander; Nicaud, Cyril; Myasnikov, Alexei; Lohrey, Markus - Berlin : de Gruyter, 2020. - XII, 374 Seiten - (GAGTA BOOK ; 1). ISBN: 978-3-11-066491-1 / 3-11-066491-7.
- Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems - Bartholdi, Laurent; Figelius, Michael; Lohrey, Markus; Weiss, Armin - Cornell University : arXiv.org, 2019. - 42 pp..
- Fixed points and stable images of endomorphisms for the free group of rank two - Ciobanu, Laura; Logan, Alan D. - Amsterdam : Elsevier, 2022. - pp. 538-576 - (Journal of Algebra ; 591. 2022).
- The Post Correspondence Problem and equalisers for certain free group and monoid morphisms - Ciobanu, Laura; Logan, Alan D. - Cornell University : arXiv.org, 2020. - 16 pp..
Schedule
The field of combinatorial group theory, a part of abstract algebra, is tightly linked to computational problems from its early days. Already in 1911, i.e., 25 years before Turing's work on the halting problem appeared, Dehn posed three group theoretical decision problems: the word problem, the conjugacy problem, and the isomorphism problem. These fundamental problems turned out to be undecidable in general for finitely presented groups by the work of Adian, Boone, Novikov and Rabin in the 1950's. Despite these negative results, for many concrete classes of groups decidability results were obtained. For instance, the word problem was shown to be decidable for one-relator groups, finitely generated linear groups, hyperbolic groups, and automatic groups.
With the rise of complexity theory in the 1960's, also the computational complexity of group theoretic problems moved into the focus of research. From the very beginning, this field attracted researchers from mathematics as well as computer science. Using algorithmic techniques from complexity theory, researchers were able to exhibit highly efficient algorithms for groups, where initially only pure decidability results have been known. A milestone in this context is Lipton and Zalcstein's logspace algorithm for the word problem of finitely generated linear groups. This was the first result putting the word problem for an important class of groups into a complexity class below polynomial time. In the last 10 years, researchers pushed the limits further towards small circuit complexity classes. In particular, the class TC^0 turned out be very important in this context; it is the class of problems that can be solved with (uniform) constant-depth threshold circuits of polynomial size. TC^0 turns out to be the smallest complexity class where the basic arithmetic operations (addition, multiplication, division) on binary encoded integers can be carried out. Although constant-depth threshold circuits of polynomial size seem to be an extremely restricted computational model, many important word and conjugacy problems were shown to be in TC^0. An example is the word problem for a finitely generated solvable linear group.
Circuit complexity is only one among several areas, where we have seen fruitful interactions between group theory and theoretical computer science in recent years. Let us mention some further examples:
- Compression techniques: Techniques from data compression turned out to be a key tool for achieving the currently best known complexity bound for various word problems and solving word equations in groups.
- Automata theory: Finite automata always played an important role in semigroup theory. In group theory, finite automata have been used for the definition of important classes of groups as exemplified by the notions of automatic groups and automaton groups.
- Generic-case complexity: Many algorithmic problems can be solved efficiently on a large set of inputs, while they are difficult in the worst-case. This observation leads to generic-case complexity. A driving force for the development of generic-case complexity theory is (group-based) cryptography.
This Dagstuhl Seminar will be centered around these topics and their interconnections. We are convinced that pushing forward the area of algorithmic group theory needs joint efforts by computer scientists and group theorists. We plan to bring together experts in group theory as well as computer science, in particular circuit complexity, automata theory and compression techniques. The seminar will provide a unique possibility for the exchange of ideas between these areas. Survey talks by leading experts will provide background to all participants.
Creative Commons BY 3.0 DE
Volker Diekert, Olga Kharlampovic, Markus Lohrey, and Alexei Myasnikov
The field of combinatorial group theory, a part of abstract algebra, is tightly linked to computational problems from its early days. Already in 1911, i.e., 25 years before Turing's work on the halting problem appeared, Max Dehn introduced and investigated three fundamental group theoretical decision problems: the word problem, the conjugacy problem, and the isomorphism problem. Dehn's problems had a strong influence on the development of modern theoretical computer science. It took more that 40 years before the work of Novikov, Boone, Adjan, and Rabin showed the undecidability of Dehn's decision problems in the class of finitely presented groups. Despite these negative results, for many groups the word problem turned out to be decidable in many important classes of groups. With the rise of complexity theory in the 1960's, also the computational complexity of group theoretic problems moved into the focus of research. From the very beginning, this field attracted researchers from mathematics as well as computer science. Using algorithmic techniques from complexity theory, researchers were able to exhibit highly efficient algorithms for groups, where initially only pure decidability results have been known. A milestone in this context is Lipton and Zalcstein's logspace algorithm for the word problem of finitely generated linear groups. This was the first result putting the word problem for an important class of groups into a complexity class below polynomial time. In the last 10 years, researchers pushed the limits further towards small circuit complexity classes. In particular the class TC^0 turned out be very important in this context. Despite its limited computational power many important group theoretical problems problems were shown to be in TC^0.
Complexity theoretical questions are not the only area where we have seen fruitful interactions between group theory and theoretical computer science in recent years. Other examples can be found in automata theory, data compression, model theory, and reachability problems for infinite state systems. The following paragraphs put some of the seminar talks into the context of these topics and mentions some of the open problems that were discussed during the seminar.
Groups and circuit complexity
Howard Straubing gave an excellent survey on circuit complexity that was particularly addressed to non-experts in complexity theory. Barrington's famous result according to which the word problem for every finite non-solvable groups is hard for NC^1 was explained and several important results centered around the circuit complexity class TC^0 were surveyed. In recent years, TC^0 turned out to be the right class for characterizing the complexity of several group theoretical problems. Two seminar talks presented further examples of group theory problems in TC^0: Armin Weiß gave a talk about the power word problem which is a succinct version of the classical word problem, where powers g^n of group elements with binary encoded integer exponents n are allowed in the input. Despite this succinctness, several power word problems (e.g. for nilpotent groups and certain wreath products of finitely generated abelian groups) can be still solved in TC^0. Moses Ganardi talked on the knapsack problem for finitely generated groups which asks for the solvability of certain exponent equations over a group. Among other results he gave a simple proof showing that the knapsack problem for unary encoded integers is in TC^0. This result generalizes to all finitely generated abelian groups.
Several promising open problems related to the circuit complexity of group theoretical problems were discussed in the open problem sessions: The above mentioned result of Barrington on finite non-solvable groups motivates the question whether the word problem for every finitely generated solvable group is NC^1-hard.Also finding new classes of infinite groups with a word problem in TC^0 is an open research problem that was intensively discussed during the seminar. So far, it is known that solvable linear groups have a word problem in TC^0 and that the class of groups with a word problem in TC^0 is closed under wreath products.
Compression techniques in group theory
Compression techniques turned out to be an important tool for obtaining efficient algorithms in group theory. The general philosophy is trying to avoid storing extremely long words by computing on a compressed representation of these words. This led to the formulation of several succinct versions of classical group theoretical problems, where the group elements in the input are given a succinct version. The power word problem that was introduced by Armin Weiß (see the previous paragraph) is such a succinct problem. The main result of Armin Weiß' talk was an efficient reduction of the power word problem for a free group to the (ordinary) word problem of a free group. It is open whether similar reductions also exist for right-angeled Artin groups and hyperbolic groups.
In the context of solving equations over groups and monoids, the so-called recompression technique led to several important results in recent years. Arthur Jez (the inventor of this technique) gave a talk on recompression and outlined his non-deterministic linear time algorithm for solvability of word equations. Ciobanu and Elder presented their recent work on equations in hyperbolic groups where they use recompression in order to show that the set of all solutions for a system of equations over a hyperbolic group is an EDT0L language.
Groups and model theory
This research area directly relates to the previous paragraph. The goal is to understand the first-order theory of groups. Of particular interest is the Diophantine theory. Decidability of the Diophantine theory means that one can decide whether a boolean combination of word equations has a solution. Olga Kharlampovich gave a talk about Diophantine theories of metabelian groups. She proved decidability for several important metabelian groups: Baumslag-Solitar groups BS(1,n) and wreath products mathbb{Z} wr mathbb{Z} and mathbb{Z}_n wr mathbb{Z}. Albert Garreta continued this topic and talked about Diophantine theories of solvable groups. He presented a large class of solvable groups (containing for instance all finitely generated non-virtually abelian nilpotent groups and all polycyclic groups that are not virtually metabelian) for which the Diophantine theory is at least as hard as the Diophantine theory of a suitable ring of algebraic integers. This leads to the conjecture that for each member of his family the Diophantine theory is undecidable.
Montserrat Casals-Ruiz talked on the positive theory of groups acting on trees. The positive theory of a group contains all negation-free statements from the full first-order theory. Montserrat Casals-Ruiz proved that many natural examples of groups acting on trees have the same positive theory as a free group of rank two. Ilya Kazachkov presented new results on the full first-order theory of free products and, more generally, graph products of groups. He showed that under certain conditions, elementary equivalent free products (meaning that their first-order theories coincide) must have elementary equivalent factors.
Groups and automata
Besides complexity of algorithmic problems, a very interesting connection between group theory and theoretical computer science is provided by automata theory, using the very flexible and algorithmically efficient finite state automata to somehow describe an infinite group. This led to the development of automatic groups and automaton groups. Automaton groups are a subclass of so-called self-similar groups. Laurent Bartholdi gave a talk on algorithmic results on self-similar groups and outlined the proof of a recent breakthrough result of Bartholdi and Mitrofanov stating that there exist self-similar groups with an undecidable word problem. For the particular case of automaton groups the word problem belongs to PSPACE. The question whether there exist automaton groups with a PSPACE-complete word problem was intensively discussed during the seminar. Recently, as a direct outcome of the seminar, an automaton group with this property was constructed by Jan Philipp Wächter and Armin Weiß [An automaton group with PSPACE-complete word problem, arXiv, 2019. https://arxiv.org/abs/1906.03424]. Volodia Nekrashevych presented in his talk a generalization of automaton groups based on non-deterministic synchronous automata-transducers and discussed their algorithmic properties and relationship to dynamical systems.
Reachability problems
The study of reachability problems for matrix semigroups has a long tradition in theoretical computer science. Formulated in terms of algebra, the reachability problem is equivalent to the subsemigroup membership problem. Several variants and generalization (rational subset membership problem, knapsack problem) have been recently investigated as well. Igor Potapov gave a survey talk on recent progress on the matrix reachability problem from a computer science perspective. Georg Zetzsche presented several new decidability results for the rational subset membership problem in wreath products. Moses Ganardi talked on wreath products as well, but put the focus on the knapsack problem.
The above talks and the open problem session identified several interersting open problems related to reachability problems. An outstanding open problem in this context asks whether the submonoid membership problem for the group GL_3(mathbb{Z}) is decidable. Recently it was shown that the submonoid membership problem for the Heisenberg group (a subgroup of GL_3(mathbb{Z})) is decidable, This result suggests two generalizations: (i) the rational subset membership problem for Heisenberg groups and (ii) the submonoid membership problem for groups of unitriangular integer matrices. In both case it is open whether the problem is decidable. Georg Zetzsche mentioned in his talk the submonoid membership problem and the rational subset membership problem in the Baumslag-Solitar group BS(1,2) as open research problems.
Concluding remarks and future plans
The seminar was well received as witnessed by the high rate of accepted invitations. There was a good balance between participants from computer science and pure mathematics, and this mixture led to many active discussions and the discovery of new connections and promising open problems. The organizers regard this seminar as a great success. With steadily increasing interactions between such researchers, we foresee another seminar focusing on the interplay between computer science and group theory. Finally, the organizers wish to express their gratitude to the Scientific Directors of the Dagstuhl Centre for their support of the seminar.
Volker Diekert, Olga Kharlampovic, Markus Lohrey, and Alexei Myasnikov
- Yago Antolin (Universidad Autónoma de Madrid, ES) [dblp]
- Laurent Bartholdi (Institute of advanced Studies, ENS Lyon, FR & Universität Göttingen, DE) [dblp]
- Montserrat Casals-Ruiz (University of the Basque Country - Biblao, ES)
- Laura Ciobanu (Heriot-Watt University - Edinburgh, GB) [dblp]
- Jordi Delgado Rodriguez (University of Porto, PT) [dblp]
- Volker Diekert (Universität Stuttgart, DE) [dblp]
- Andrew Duncan (Newcastle University, GB) [dblp]
- Bettina Eick (TU Braunschweig, DE) [dblp]
- Murray Elder (University of Technology - Sydney, AU) [dblp]
- Michal Ferov (University of Newcastle - Callaghan, AU) [dblp]
- Michael Figelius (Universität Siegen, DE)
- Moses Ganardi (Universität Siegen, DE) [dblp]
- Albert Garreta Fontelles (University of the Basque Country - Biblao, ES) [dblp]
- Susan Hermiller (University of Nebraska - Lincoln, US)
- Artur Jez (University of Wroclaw, PL) [dblp]
- Ilya Kapovich (City University of New York, US) [dblp]
- Ilya Kazachkov (University of the Basque Country, ES & Ikerbasque - Bilbao, ES) [dblp]
- Olga Kharlampovic (The City University of New York, US) [dblp]
- Manfred Kufleitner (Loughborough University, GB) [dblp]
- Markus Lohrey (Universität Siegen, DE) [dblp]
- Alexei Myasnikov (Stevens Institute of Technology - Hoboken, US) [dblp]
- Volodymyr Nekrashevych (Texas A&M University - College Station, US) [dblp]
- Gretchen Ostheimer (Hofstra University - Hempstead, US) [dblp]
- Igor Potapov (University of Liverpool, GB) [dblp]
- Timothy Riley (Cornell University, US)
- Paul E. Schupp (University of Illinois - Urbana Champaign, US) [dblp]
- Géraud Sénizergues (University of Bordeaux, FR) [dblp]
- Vladimir Shpilrain (City University of New York, US) [dblp]
- Rachel Skipper (Binghamton University, US) [dblp]
- Tatiana Smirnova-Nagnibeda (University of Geneva, CH) [dblp]
- Benjamin Steinberg (City University of New York, US) [dblp]
- Howard Straubing (Boston College, US) [dblp]
- Svetla Vassileva (Champlain Regional College - St. Lambert, CA) [dblp]
- Alina Vdovina (Newcastle University, GB) [dblp]
- Enric Ventura Capell (UPC - Barcelona Tech, ES) [dblp]
- Pascal Weil (University of Bordeaux, FR) [dblp]
- Armin Weiß (Universität Stuttgart, DE) [dblp]
- Georg Zetzsche (MPI-SWS - Kaiserslautern, DE) [dblp]
Classification
- data structures / algorithms / complexity
Keywords
- group theory
- circuit complexity
- finite automata
- algorithms on compressed structures
- generic-case complexity
