On complexity of the word problem in braid groups and mapping class groups (Q1578891)

The paper deals with (uniform) word problems of the mapping class groups and other related groups. The author proves that the word problem of the mapping class group \(M^p_g\) of the surface of genus \(g\) with \(p\) punctures has complexity \(O(|w|^2(g+p)+|w|(g+p)\log(g+p))\), where \(|w|\) is the length of a word \(w\), the complexity for the braid group \(B_n\) is \(O(n|w|^2+|w|n\log n)\), while the complexity for the closed surface with genus \(g\) is \(O(|w|^2g^2+|w|g^2\log g)\). The author computes the complexity of the action of a given element of the mapping class group on the space of measured train-tracks on the surface. For the complexity of the braid group \(B_n\) he uses the exact sequences: \(1\to M^{n+1}_0\to\widetilde M^{n+1}_0\to S_n\to 1\) and \(1\to\mathbb{Z}\to B_n\to\widetilde M^{n+1}_0\to 1\), where \(\widetilde M^{n+1}_0\) is the extended mapping class group allowing permutations of punctures and \(S_n\) is the symmetric group of degree \(n\).