Myasnikov (City College of New York) et al. apply the complexity of non-commutative groups
to public key cryptography, assess the generic-case performance of various algorithms, and …

This book is about relations between three di? erent areas of mathematics and
theoreticalcomputer science: combinatorialgroup theory, cryptography, and c-plexity theory …

This survey is intended to be a fast (and reasonably updated) reference for the theory of
Stallings automata and its applications to the study of subgroups of the free group, with the …

It is shown that the subgroup membership problem for a virtually free group can be decided
in polynomial time when all group elements are represented by so-called power words, ie …

The goalofthisbookis toshowcasenewdirectionsingroup theorymotivated bycomputer
science. The subtitle (GAGTA book) reflects the fact that the book follows the courseoftheGeometricandAsymptoticGroup …

We show that one can define and effectively compute Stallings graphs for quasi-convex
subgroups of automatic groups (eg hyperbolic groups or right-angled Artin groups). These …

This text, Chapter 23 in the" AutoMathA" handbook, is devoted to the study of rational
subsets of groups, with particular emphasis on the automata-theoretic approach to finitely …

The Whitehead minimization problem consists in finding a minimum size element in the
automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank …

In this paper we discuss generic properties of “random subgroups” of a given group G. It
turns out that in many groups G (even in most exotic of them) the random subgroups have a …

We study the average case complexity of the Uniform Membership Problem for subgroups of
free groups, and we show that it is orders of magnitude smaller than the worst case …