[Geometry, Topology and Dynamics Seminar] Topology on tiny machines: logspace and finite-state complexity by Ben Burton (University of Queensland)

Instead of the usual focus on time complexity, here we discuss the space complexity of topological algorithms.  We explain how to test 2-manifolds for homeomorphism in logspace (joint with Elder, Kalka and Tillmann), and we prove a variety of positive and negative results for 3-dimensional problems on finite state tree automata (joint with Fellows).