Spring 2007 New York Group Theory Seminar

Fridays at 4 p.m.

Department of Mathematics
CUNY, Graduate Center

365 Fifth Avenue at 34th Street, 5th Floor, Room 5417
Fridays at 4:00 p.m.
Tea served beforehand at 3:30 p.m. in Mathematics Lounge, 4th floor.

Saul Schleimer, Rutgers University

Polynomial-time word problems

Following a paper of Markus Lohrey, we will discuss the compressed word problem for a group G. We will then reduce the regular word problem for finitely generated subgroups of Aut(G) to the compressed word problem for G. This gives a polynomial-time algorithm solving the word problem for Aut(F_n), as well as a new solution to the word problem in the mapping class group. Time permitting, I will sketch a work-in-progress with Markus Lohrey: a solution to the compressed word problem for right-angled Artin groups.

Friday, April 27th
Tea: 3:30 p.m. 4th Floor Mathematics Lounge
Seminar: 4 p.m. 5th Floor, Room 5417

The New York Group Theory Seminar and some of the associated conferences are supported by funds from the National Science Foundation, Dean of Science, Maria Tamargo and Dean of Engineering, Joe Barba.

Back to NYGTC