Conference abstracts

Session A4 - Computational Geometry and Topology

July 12, 15:00 ~ 15:25 - Room B7

Topology on tiny machines: logspace and finite-state complexity

Benjamin Burton

The University of Queensland, Australia   -   bab@maths.uq.edu.au

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).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.