Tractable topological computing: Escaping the hardness trap (2015–2023)
Abstract:
Computational topology is a young and energetic field that uses computers to solve complex geometric
problems driven by pure mathematics, and with diverse applications in biology, signal processing and data
mining. A major barrier is that many of these problems are thought to be fundamentally and intractably hard.
This project will defy such barriers for typical real-world inputs by fusing geometric techniques with
technologies from the field of parameterised complexity, creating powerful, practical solutions for these
problems. It will shed much-needed light on the vast and puzzling gap between theory and practice, and give
researchers fast new software tools for large-scale experimentation and cutting-edge computer proofs.