Håvard Bakke Bjerkevik: Computational complexity in persistence

Abstract

 For topological data analysis to be useful, we need efficient algorithms for computation. Our hunt for computational efficiency involves understanding which problems are NP-hard, and which problems might allow polynomial time algorithms. It is known that computing the interleaving distance for merge trees and multiparameter modules is NP-hard, and in recent work, Magnus Botnan and I proved that NP-hardness also holds in these cases for \(\ell^p\)-versions of the interleaving distances. I will discuss these results and related classes of problems for which the computational complexity is still poorly understood. This includes an important meta-question in multiparameter persistence; namely, how much information do we have to sacrifice to turn a hard problem into a tractable one?