Seminar series
Date
Tue, 04 Feb 2014
Time
17:00 -
18:00
Location
C5
Speaker
Tim Riley
Organisation
Cornell University
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.