English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The worst-case complexity of group-theoretic algorithms has been studied fora long time. Generic-case complexity, or complexity on random inputs, wasintroduced and studied relatively recently. In this paper, we address theaverage-case complexity (i.e., the expected runtime) of algorithms that solve awell-known problem, the Whitehead problem in a free group, which is: given twoelements of a free group, find out whether there is an automorphism that takesone element to the other. First we address a special case of the Whiteheadproblem, namely deciding if a given element of a free group is part of a freebasis. We show that there is an algorithm that, on a cyclically reduced inputword, solves this problem and has constant (with respect to the length of theinput) average-case complexity. For the general Whitehead problem, we show thatthe classical Whitehead algorithm has linear average-case complexity if therank of the free group is 2. We argue that the same should be true in a freegroup of any rank but point out obstacles to establishing this general result.

Average-case complexity of the Whitehead problem for a free group