Tractable topological computing: Escaping the hardness trap (2015–2017)

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.
Grant type:
ARC Discovery Projects
Funded by:
Australian Research Council