Presented by: 
Ben Burton, UQ
Date: 
Tue 1 Sep, 3:00 pm - 4:00 pm
Venue: 
Building 67, Room 442

In theory, computation with knots and 3-manifolds is extremely difficult.  However, there is a growing realisation that there is an enormous gap between theory and practice: with real software and a typical desktop computer we can often solve difficult problems with knots and 3-manifolds that were once thought to be hopelessly difficult.  In this talk we look beyond the real of desktop computers, and examine what happens to these and related problems when we impose far more severe constraints on our computational power.

Our main focus is on machines with very limited memory. where we give both positive and negative results.  For instance, we show that testing two surfaces for topological equivalence can be done in logarithmic space, and we show that recognising the 2-sphere is finite state for triangulations of bounded treewidth but that recognising the 3-sphere is not.

Includes joint work with Murray Elder, Mike Fellows and Stephan Tillmann.