https://www.dagstuhl.de/19131

March 24 – 29 , 2019, Dagstuhl Seminar 19131

Algorithmic Problems in Group Theory

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)

For support, please contact

Annette Beyer for administrative matters

Michael Gerke for scientific matters

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

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support