Abstract:

PLEASE NOTE THE NEW ROOM - AMADO 719

Abstract: I will talk about a recent result of Frank Wagner and myself, where we prove that S-machines can emulate Turing machines in quasilinear time. This implies, for example, that a group G whose word problem can be solved in time T(n) can be isometrically embedded into a finitely presented group H such that the Dehn function of H is at most $n^2 T(n^2)^{2+\epsilon}$, and the Dehn function of G in H is at most $T(n)^{2+\epsilon}$, improving the bounds of Sapir, Birget, Rips, and Ol'shanskii ($n^2 T(n^2)^4$ and $T(n)^4$ respectively).