# 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)

### 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?