Taming the hydra: the word problem and extreme integer compression

For a finitely presented group, the Word Problem asks for an algorithm

which declares whether or not words on the generators represent the

identity. The Dehn function is the time-complexity of a direct attack

on the Word Problem by applying the defining relations.

A "hydra phenomenon" gives rise to novel groups with extremely fast

growing (Ackermannian) Dehn functions. I will explain why,

nevertheless, there are efficient (polynomial time) solutions to the

Word Problems of these groups. The main innovation is a means of

computing efficiently with compressed forms of enormous integers.

This is joint work with Will Dison and Eduard Einstein.