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 lower than the worst case complexity of the best known algorithms. This applies both to subgroups given by a fixed number of generators, and to subgroups given by an exponential number of generators. The main idea behind this result is to exploit a generic property of tuples of words, called the central tree property. Another application is given to the average case complexity of the relative primitivity problem, using Shpilrain’s recent algorithm to decide primitivity in a free group, whose average case complexity is a constant depending only on the rank of the ambient free group.
Joint work with Pascal Weil and Mallika Roy.
This video is part of the New York Group Theory Cooperative‘s group theory seminar series.
