Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression

Computer Science/Discrete Mathematics Seminar II
Topic:Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression
Speaker:Timothy Riley
Affiliation:Cornell University; Member, School of Mathematics
Date:Tuesday, December 2
Time/Room:10:30am - 12:30pm/S-101
Video Link:http://video.ias.edu/csdm/2014/1202-TimothyRiley

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. I will survey these topics and their interrelationships. 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.