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


Wednesday, March 20, 2019 - 16:00 to 17:00


Lab 3, B700


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

All-OIST Category: 

Subscribe to the OIST Calendar: Right-click to download, then open in your calendar application.