Session A4 - Computational Geometry and Topology
July 12, 15:00 ~ 15:25 - Room B7
Topology on tiny machines: logspace and finite-state complexity
The University of Queensland, Australia - firstname.lastname@example.org
Instead of the usual focus on time complexity, here we discuss the space complexity of topological algorithms. We show that you can 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).