Skip to main content

Håvard Bakke Bjerkevik: Computational complexity in persistence

Time: Tue 2024-05-28 10.15

Location: KTH 3418, Lindstedtsvägen 25 and Zoom

Video link: Meeting ID: 632 2469 3290

Participating: Håvard Bakke Bjerkevik (New York State University at Albany)

Export to calendar

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?