https://www.dagstuhl.de/19131

24. – 29. März 2019, Dagstuhl Seminar 19131

Algorithmic Problems in Group Theory

Organisatoren

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, US)

Auskunft zu diesem Dagstuhl Seminar erteilen

Annette Beyer zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

Motivation

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.

License
  Creative Commons BY 3.0 DE
  Volker Diekert, Olga Kharlampovic, Markus Lohrey, and Alexei Myasnikov

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Group theory
  • Circuit complexity
  • Finite automata
  • Algorithms on compressed structures
  • Generic-case complexity

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.