This project is funded by the Austrian Science Fund (FWF) under
grant P 29984-N35 (2017-21).
The last 15 years have witnessed an increasing research activity on
the interface of topological invariants from algebraic topology and
the qualitative analysis of data. This has led to the new and rapidly
evolving field of topological data analysis (tda). Due to the ever-increasing
size and complexity of real data, the key question for the success of the
discipline is: how can this mathematically sophisticated theory be applied
on large scale data sets?
This project will contribute novel algorithmic approaches into the
major steps of the computational pipeline of tda.
In particular, it introduces new techniques into the popular
field of approximating filtrations of simplicial complexes,
it extends previous successes for the computation
of persistent homology to more general and challenging scenarios,
and it provides fast algorithms for the comparison of
persistence diagrams and related topological invariants.
The goal is to advance the pioneer works in these fields to the first mature
algorithmic solutions usable for large scale data sets as they occur
in application scenarios.
Besides these application-driven goals,
the project also aims for an improved theoretical understanding of the
potentials and the limitations of currently existing and newly developed
We focus on algorithms with provable formal guarantees through
asymptotic worst-case analysis and quality bounds for approximation algorithms.
At the same time, we aim for practical solutions and investigate
the quality of our solution through careful implementation work.
We will release successful implementation in the form of publicly available
software packages. We expect from this comprehensive point of view to
create a far more substantial impact on the field of computational topology
than by concentrating solely on a single aspect.
The list of publications below also includes work performed before
the runtime of the grant.
- Michael Kerber, Michael Lesnick, Steve Oudot: Exact computation of the matching distance on 2-parameter persistence modules. Accepted for the 35th International Symposium on Computational Geometry (SoCG 2019). Available at arXiv:1812.09085.
- Ulderico Fugacci, Michael Kerber: Chunk Reduction for Multi-Parameter Persistent Homology. Accepted for the 35th International Symposium on Computational Geometry (SoCG 2019). Available at arXiv:1812.08580.
- Clement Maria, Hannah Schreiber: Discrete Morse Theory for Computing Zigzag Persistence. arXiv:1807.05172.
- Michael Kerber, Arnur Nigmetov: Metric Spaces with Expensive Distances. arXiv:1901.08805.
- Havard Bjerkevik, Magnus Botnan, Michael Kerber: Computing the interleaving distance is NP-hard. arXiv:1811.09165.
- Aruni Choudhary, Michael Kerber, Sharath Raghvendra: Improved Topological Approximations by Digitization. Accepted for Symposium on Discrete Algorithms (SODA 2019). Available at arXiv:1812.04966
- Rene Corbet, Ulderico Fugacci, Michael Kerber, Claudia Landi, Bei Wang: A Kernel for Multi-Parameter Persistent Homology. arXiv:1809.10231.
- Rene Corbet, Michael Kerber: The Representation Theorem of Persistent Homology Revisited and Generalized. Journal of Applied and Computational Topology (link) Available at arXiv:1707.08864.
- Michael Kerber, Hannah Schreiber: Barcodes of Towers and a Streaming Algorithm for Persistent Homology. Discrete and Computational Geometry (link). The conference version appeared at the 33rd International Symposium on Computational Geometry (SoCG 2017).
- Aruni Choudhary, Michael Kerber, Sharath Raghvendra: Improved Approximate Rips Filtrations with Shifted Integer Lattices. European Symposium on Algorithms (ESA 2017), pp. 28:1-28:13. Available at arXiv:1706.07399.
- Aruni Choudhary, Michael Kerber, Sharath Raghvendra: Polynomial-Sized Topological Approximations Using The Permutahedron. Discrete and Computational Geometry (link).
The conference version appeared at the 32nd International Symposium on Computational Geometry (SoCG 2016), pp.31:1-31:16, 2016 (link). Also available at arXiv:1601.02732.
- Ulrich Bauer, Michael Kerber, Jan Reininghaus, Hubert Wagner: PHAT - Persistent Homology Algorithms Toolbox. Journal of Symbolic Computation - Special Issue on Algorithms and Software for Computational Topology (In Press). (pdf)
© Elsevier 2016. The website of the article is http://dx.doi.org/10.1016/j.jsc.2016.03.008. A short version appeared at the 4th International Congress of Mathematical Software (ICMS 2014).
- Michael Kerber, Dmitriy Morozov, Arnur Nigmetov: Geometry helps to Compare Persistence Diagrams. Journal of Experimental Algorithms 22, 2017 (link). A conference version appeared at ALENEX 2016, pp.103-112 (pdf) © SIAM 2016.
- Michael Kerber, Don Sheehy, Primoz Skraba: Persistent Homology and Nested Dissection. ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp.1234-1245. (pdf) © SIAM 2016.