10:00 (EDT) / 15:00 (CET): Herbert Edelsbrunner

Title: Dynamically maintaining the persistent homology of linear and cyclic lists

Abstract: We present a dynamic data structure for maintaining the persistent homology of linear and cyclic lists of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and gluing of lists, each in time $O(\log n + k)$, in which $n$ is the number of minima and maxima and $k$ is the number of changes in the persistent homology. We evaluate the performance of the data structure experimentally by applying its implementation to random data and by comparing the running-time with those of traditional approaches to computing persistent homology.

This is joint work with Sebastiano Cultrera, Monika Henzinger, and Wolfgang Ost.

10:30 (EDT) / 15:30 (CET): Primoz Skraba

Title: Learning Homological Stratifications

Abstract: The focus of this talk will be an algorithm (and sufficient conditions) for reconstructing a structure of a stratified space. In general, we will be interested in the homological stratification, where changes in local structure can be detected using local homology. Now while finding the homology of a space from samples has been extensively studied from a number of perspectives – extending this to finding stratifications has been a challenge for over a decade. We will show that from a finite sample of a stratified space, we can recover a stratification which is close to the original stratification in a precise sense. While the algorithm holds quite generally, most of the talk will focus on the piecewise-linear case in order to minimize technicalities. The talk will not assume any prior knowledge of stratifications or local homology,

11:00 (EDT) / 16:00 (CET): Wojtek Chacolski

Title: Homological algebra and persistence

Abstract: There is a growing interest in TDA community regarding homological invariants of persistent modules. In my talk I will describe a set up for relative homological algebra with computationally effective methods based on Koszul complexes for calculating associated Betti diagrams.

This is a join work with A. Guidolin, I. Ren, M. Scolamiero, F. Tombari

12:30 (EDT) / 17:30 (CET): Woojin Kim

Title: Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence

Abstract: The notion of generalized rank invariant in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. Naturally, computing these rank invariants efficiently is a prelude to computing any of these derived structures efficiently. We show that the generalized rank over a finite interval I of a Z2-indexed persistence module M is equal to the generalized rank of the zigzag module that is induced on a certain path in I tracing mostly its boundary. Hence, we can compute the generalized rank over I by computing the barcode of the zigzag module obtained by restricting the bifiltration inducing M to that path. If the bifiltration and I have at most t simplices and points respectively, this computation takes O(t^ω) time where ω ∈ [2, 2.373) is the exponent of matrix multiplication. Among others, we apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module M, determine whether M is interval decomposable and, if so, compute all intervals supporting its summands.

This is joint work with Tamal Dey and Facundo Mémoli.

13:00 (EDT) / 18:00 (CET): Zhengchao Wan

Title: Persistent Laplacians: properties, algorithms and implications

Abstract: In this work we present a thorough study of the theoretical properties and devise efficient algorithms for the persistent Laplacian, an extension of the standard combinatorial Laplacian to the setting of simplicial pairs: pairs of simplicial complexes related by an inclusion, which was introduced by Wang, Nguyen, and Wei.
In analogy with the non-persistent case, we establish that the nullity of the q-th persistent Laplacian equals the q-th persistent Betti number of any given simplicial pair which provides an interesting connection between spectral graph theory and TDA.
We further exhibit a novel relationship between the persistentLaplacian and the notion of Schur complement of a matrix. This relation permits us to uncover a link with the notion of effective resistance from network circuit theory and leads to a persistent version of the Cheeger inequality.
This relationship also leads to a novel and fundamentally different algorithm for computing the persistent Betti number for a pair of simplicial complexes which can be significantly more efficient than standard algorithms.

10:00 (EDT) / 15:00 (CET): Luis Scoccola

Title: Bottleneck stable invariants of multiparameter persistence modules via relative homological algebra

Abstract: Unlike one-parameter persistence modules, for which we have the barcode, persistence modules with two or more parameters do not admit a complete discrete invariant, and thus incomplete invariants must be used to study the structure of such modules in practice. The Hilbert function and the multigraded Betti numbers are among the simplest such incomplete invariants, and, although these invariants are already being used in applications, it is a priori unclear whether they satisfy a stability result analogous to the stability of the one-parameter barcode. I will present joint works with Oudot and with Botnan, Oppermann, and Oudot in which we prove bottleneck stability results for multigraded Betti numbers and the Hilbert function, as well as for finer invariants coming from projective resolutions in certain exact structures on categories of multiparameter persistence modules.

10:30 (EDT) / 15:30 (CET): Tung Lam

Title: $\ell^p$-type Metric on Merge Trees

Abstract: We generalize the interleaving distance on merge trees to an $\ell^p$-type distance by adapting Bjerkevik and Lesnick's definition in the recent work on multiparameter persistence modules. Our $\ell^p$-type distance is a metric on isomorphism classes of merge trees, and concides with the interleaving distance when $p=\infty$. We show that our distance upper-bounds the $p$-Wasserstein distance on barcodes of associated merge trees. Building on an idea of Skraba and Turner on Cellular Wasserstein stability, we show that our distance is stable with respect to cellular sublevel-set filtration and in fact, universal for any $p \in [1, \infty]$. For the case $p=\infty$, this gives a novel proof of universality for the interleaving distance on merge trees.

This is joint work with R. Cardona, J. Curry, and M. Lesnick at SUNY Albany.

11:00 (EDT) / 16:00 (CET): Erin Chambers

Title: On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class

Abstract: Homology features of spaces which appear in applications, for instance 3D meshes, are among the most important topological properties of these objects. Given a non-trivial cycle in a homology class, we consider the problem of computing a representative in that homology class which is optimal. We study two measures of optimality, namely, the lexicographic order of cycles (the lex-optimal cycle) and the bottleneck norm (a bottleneck-optimal cycle). We give a simple algorithm for computing the lex-optimal cycle for a 1-homology class in a closed orientable surface. In contrast to this, our main result is that, in the case of 3-manifolds of size n² in the Euclidean 3-space, the problem of finding a bottleneck optimal cycle cannot be solved more efficiently than solving a system of linear equations with an n × n sparse matrix. From this reduction, we deduce several hardness results. Most notably, we show that for 3-manifolds given as a subset of the 3-space of size n², persistent homology computations are at least as hard as rank computation (for sparse matrices) while ordinary homology computations can be done in O(n² log n) time. To the best of our knowledge, this is the first such distinction between these two computations. Moreover, it follows that the same disparity exists between the height persistent homology computation and general sub-level set persistent homology computation for simplicial complexes in 3-space.

12:30 (EDT) / 17:30 (CET): Tao Hou

Title: Fast Computation of Zigzag Persistence

Abstract: In this talk, we present an algorithm called FastZigzag for computing zigzag persistence by a reduction to the computation of standard persistence. Our main result is that an input simplex-wise zigzag filtration can be converted to a cell-wise non-zigzag filtration of a Delta-complex with the same length, where the cells are copies of the input simplices. This conversion step in our algorithm incurs very little cost. Furthermore, the barcode of the original filtration can be easily read from the barcode of the new cell-wise filtration because the conversion embodies a series of the Mayer-Vietoris diamond switches. This seemingly simple observation opens up the vast possibilities for improving the computation of zigzag persistence because any efficient algorithm/software for standard persistence can now be applied to computing zigzag persistence. Our experiment shows that this indeed achieves substantial performance gain.

This is joint work with Tamal K. Dey.

13:00 (EDT) / 18:00 (CET): Nicolas Berkouk

Title: Projected barcodes and distances for multi-parameter persistence

Abstract: In this talk, we will present a new class of invariants of multi-parameter persistence modules : projected barcodes. Relying on Grothendieck's six operations for sheaves, projected barcodes are defined as derived pushforwards of persistence modules onto R (which can be seen as sheaves on a vector space in a precise sense). We will prove that the well-known fibered barcode is a particular instance of projected barcodes. Moreover, our construction is able to distinguish persistence modules that have the same fibered barcodes but are not isomorphic. We will present a systematic study of the stability of projected barcodes. Given F a subset of the 1-Lipschitz functions, this leads us to define a new class of well-behaved distances between persistence modules, the F-Integral Sheaf Metrics (F-ISM), as the supremum over p in F of the bottleneck distance of the projected barcodes by p of two persistence modules.

In the case where M is the collection in all degrees of the sublevel-sets persistence modules of a function f : X -> R^n, we prove that the projected barcode of M by a linear map p : R^n \to R is nothing but the collection of sublevel-sets barcodes of the post-composition of f by p. In particular, it can be computed using already existing softwares, without having to compute entirely M. We also provide an explicit formula for the gradient with respect to p of the bottleneck distance between projected barcodes, allowing to use a gradient ascent scheme of approximation for the linear ISM. We will conclude by presenting applications to unsupervised image classification.

This is joint work with François Petit and Luca Nyckees.

10:00 (EDT) / 15:00 (CET): Rob Ghrist

Title: Persistence & Lattices

Abstract: This talk will motivate the use of lattices in topological data analysis and persistence. After a brief overview of lattice theory and its relations to persistent homology, a tool for computation via Hodge theory will be detailed.

This represents joint independent projects with Hans Riess and Greg Henselman-Petrusek.

10:30 (EDT) / 15:30 (CET): Justin Curry

Title: Decorated Merge Trees for Persistent Topology

Abstract: In this talk I will present on recent collaborative work with Haibin Hang, Washington Mio, Tom Needham and Osman Okutan. This work develops a new tool for topological data analysis (TDA) that ties together connected component and homological information into a single data structure: the decorated merge tree (DMT). This enriched topological summary allows us to disambiguate data sets that have identical persistent homology and merge trees, but also satisfies the usual computability and stability properties that one expects in TDA. I will present three equivalent definitions of DMTs that leverages category-theoretic, poset-theoretic and sheaf-theoretic perspectives. The category-theoretic definition leads to immediate proofs of stability for functional data and the sheaf-theoretic definition points towards further generalization. If time permits, I will present some follow-up work on Decorated Reeb Graphs with the above authors and Florian Russold.

11:00 (EDT) / 16:00 (CET): Patrizio Frosini

Title: From Topological Data Analysis to Topological Observer Analysis: a new way to look at the shape of data

Abstract: The present research in data analysis suggests that the correct interpretation of data strongly depends on the geometric properties of the observers. Group equivariant non-expansive operators (GENEOs) have been recently introduced as mathematical tools for approximating data observers when data are represented by real-valued or vector-valued functions (https://rdcu.be/bP6HV). In this talk we will illustrate some recent results in the theory of GENEOs, showing how these operators can make available a new approach to topological data analysis and geometric deep learning.

12:30 (EDT) / 17:30 (CET): Michal Lipinski

Title: Tracking Dynamical Features via Continuation and Persistence

Abstract: In recent years combinatorial dynamics has become an important subject of interest. A cornerstone for combinatorial modeling of continuous dynamics were combinatorial vector fields by Robin Forman. Later, Mrozek extended Forman’s idea by proposing the theory of multivector fields. In recent papers, persistence homology has been used to study the robustness of isolated invariant sets (i.e., salient features of a combinatorial dynamical system), or to track changes in Conley index (i.e., a homological descriptor capturing the dynamical nature of an invariant set). Our current work focuses on the idea of continuation and its adaptation to combinatorial settings. Continuation captures the idea of transforming an isolated invariant set into another under continuous modification of the underlying dynamical system (e.g., a continuous change of the system’s parameter). If the Conley index remains intact during such a transformation, we say that two isolated invariant sets are related by a continuation. We introduced a ”tracking protocol,” a canonical way for studying the evolution of an isolated invariant set and its Conley index as the underlying combinatorial dynamic is changing. The protocol provides clues when the isolated invariant set goes through bifurcation-like events. We also show that the continuation is a special case of persistence of the Conley index. In order to define a continuation, we had to introduce an atomic refinement, i.e., splitting a single multivector into two, as a combinatorial counterpart of a perturbation of a combinatorial system. It imposes a topology on the space of all multivector fields. This allows us to study continuation from a more global perspective, reveals new connections to the classical theory of dynamical systems, and opens questions for further studies.

This is joint work with Tamal K. Dey, Marian Mrozek, and Ryan Slechta

13:00 (EDT) / 18:00 (CET): Ling Zhou

Title: Ephemeral persistence features and the stability of filtered chain complexes

Abstract: Ephemeral features are features with zero lifespans, which are traditionally discarded in the standard TDA pipeline since they lack persistent homology information. However, these features are prominently present at the filtered chain complex (FCC) level in the sense that they help characterize FCCs up to isomorphism.

In this talk, by building upon constructions due to Usher and Zhang in the context of FCCs, we show that ephemeral features, when combined with the standard barcode, produce a more discriminative invariant of finite metric spaces than the standard barcode alone. Also, we strengthen the usual stability theorem for Vietoris-Rips (VR) persistent homology of finite metric spaces. We then exhibit several examples with identical VR barcodes yet with different verbose VR barcodes thus confirming that these ephemeral points strengthen the standard VR barcode.

10:00 (EDT) / 15:00 (CET): Pawel Dlotko

Title: Mapper algorithms and their extensions

Abstract: There are two main working horses of TDA - Persistent homology and Mapper algorithm(s). The first provides a rich and useful data descriptor, while the former, a way of visualizing and analysing high dimensional data of low intrinsic dimension. In this talk I will discuss mapper, and its recent version, a ball mapper together with a number of knot-theory motivated extensions. I will start by discussing an equivariant ball mapper that preserves groups acting on the underlying point cloud. Subsequently I will show how mapper can be used to visualize maps between high dimensional datasets and how to combine mapper and ball mapper construction together. If time permits, I will discuss a few ideas of distances between mapper graphs.

This is joint work with Davide Gurnari and Radmila Sazdanovic.

10:30 (EDT) / 15:30 (CET): Julien Tierny

Title: Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark

Abstract: In this talk, I will present an efficient approach for persistence diagram computation, given an input piecewise linear scalar field f defined on a d-dimensional simplicial complex K, with d<=3. Our method extends the seminal "PairCells" algorithm by introducing three main accelerations. First, we express this algorithm within the setting of discrete Morse theory, which considerably reduces the number of input simplices to consider. Second, we introduce a stratification approach to the problem, that we call "sandwiching". Specifically, minima-saddle persistence pairs (D_0(f)) and saddle-maximum persistence pairs (D_{d−1}(f)) are efficiently computed by respectively processing with a Union-Find the unstable sets of 1-saddles and the stable sets of (d-1)-saddles. This fast processing of the dimensions 0 and (d-1) further reduces the number of critical simplices to consider for the computation of D_1(f), the intermediate layer of the sandwich. Third, we document several performance improvements via shared-memory parallelism. We provide an open-source implementation of our algorithm for reproducibility purposes. We also contribute a reproducible benchmark package, which exploits three-dimensional data from a public repository and compares our algorithm to a variety of publicly available implementations. Extensive experiments indicate that our algorithm improves by two orders of magnitude the time performance of the seminal "PairCells" algorithm it extends. Moreover, it also improves memory footprint and time performance over a selection of 14 competing approaches, while producing a strictly identical output. We illustrate the utility of our contributions with an application to the fast and robust extraction of persistent 1-dimensional generators on surfaces, volume data and high-dimensional point clouds.

This is joint work with Pierre Guillou and Jules Vidal.

11:00 (EDT) / 16:00 (CET): Bastian Rieck

Title: Topological Representation Learning in the Natural Sciences

Abstract: Representation learning, i.e. the data-driven extraction of task- specific representations such as point clouds, is staple of modern machine learning research. In this context, topological methods can serve as additional inductive biases, regularising learned representations to make them more robust and faithful to the data. I will discuss two different case studies for topology-based representation learning: the first one aims to deepen our understanding of the standard model of physics by analysing complex point clouds arising from particle collisions, while the second one deals with complex reconstruction tasks of biological data sets. Moreover, I will provide a gentle overview to the underlying machine learning concepts, making the talk accessible for a broader audience.

12:30 (EDT) / 17:30 (CET): Barbara Giunti

Title: Some like it sparse

Abstract: The worst-case examples of the barcode algorithm necessarily require the reduced matrix to become dense. Thus, one may ask if keeping the matrix sparse during the reduction could lead to improved performance. In this work, we present several variants of the barcode algorithm that try to keep the reduced matrix sparse. We show that two of them improve upon state-of-the-art techniques on several examples in practice. Moreover, for one of them, we obtain novel output-sensitive bounds that better explain the discrepancy between the cubic worst-case complexity bound and the very fast practical behaviour of matrix reduction.

This is joint work with Ulrich Bauer, Talha Bin Masood, Guillaume Houry, Michael Kerber, and Abhishek Rathod.

13:00 (EDT) / 18:00 (CET): Vidit Nanda

Title: How to compute persistence badly

Abstract: In this talk I will describe a very, very slow algorithm for computing the barcode decomposition of a one-parameter persistence module along with the change of basis matrices which place the input module into barcode form. What we lose in efficiency, we gain in conceptual clarity: by focusing on the steps of this algorithm, we are able to characterise the space of all the change of bases which bring the given module into barcode form. One immediate consequence of this is the ability to simplify the matrix representations of maps between persistence modules.

This is joint work with Emile Jacquard and Ulrike Tillmann.

10:00 (EDT) / 15:00 (CET): Yasu Hiraoka

Title: Is the persistence diagram really a stable data descriptor?

Abstract: It is well known that persistence diagrams stably behave under small perturbations to the input data. This is the consequence of stability theorems, firstly proved by Cohen-Steiner, Edelsbrunner, and Harer (2007), and then extended by several researchers. On the other hand, if the input data is realized in a high-dimensional space with a small noise, the curse of dimensionality (CoD) causes serious adverse effects on data analysis, especially leading to inconsistency of distances. In this talk, I will show several examples of CoD appearing in persistence diagrams (e.g., from single-cell RNA sequencing data in biology). Those examples demonstrate that the classical stability theorems are not sufficient to guarantee stable behaviors of persistence diagrams for high-dimensional data. Then I will show several mathematical results about the existence and the (partial) resolution of CoD in persistence diagrams. This is a joint work with Liu Enhao, Yusuke Imoto and Shu Kanazawa.

10:30 (EDT) / 15:30 (CET): Renata Turkes

Title: Persistent homology detects convexity

Abstract: We introduce tubular filtrations, inspired by the concept of tubular neighborhoods in differential topology, and provide both a theoretical result and computational experiments on synthetic and real-world data that demonstrate that persistent homology with respect to tubular filtrations can be used to detect convexity. This talk is based on joint work with Nina Otter and Guido Montúfar, and on the paper https://arxiv.org/abs/2206.10551.

11:00 (EDT) / 16:00 (CET): Havard Bjerkevik

Title: Quasi-Universality of Reeb Graph Distances

Abstract: I will talk about recent work with Ulrich Bauer and Benedikt Fluhr where we establish bi-Lipschitz bounds certifying quasi-universality (universality up to a constant factor) for various distances between Reeb graphs: the interleaving distance, the functional distortion distance, and the functional contortion distance. The definition of the latter distance is a novel contribution, and for the special case of contour trees we also prove strict universality of this distance. Furthermore, we prove that for the special case of merge trees the functional contortion distance coincides with the interleaving distance, yielding universality of all four distances in this case.

If time allows, I will also discuss tightness of these bounds and the complexity of computing quasi-universal distances.

See https://drops.dagstuhl.de/opus/volltexte/2022/16022/ for more details.

12:30 (EDT) / 17:30 (CET): Fabian Roll

Title: Functorial nerve theorems for persistence

Abstract: The history of the nerve construction goes back at least to Alexandrov (1928) and the early days of algebraic topology. Nowadays, the nerve theorem, as well as the aspect of functoriality, play a crucial role in topological data analysis. Nerves of closed covers, such as the Čech and Delaunay complex, are one of the main tools to replace a point cloud with a combinatorial model that captures the shape of the data and that is suitable for computations. In this talk, I will give a short introduction to the topic and sketch a proof of the functorial nerve theorem for covers by closed convex sets in Euclidean space that uses relatively elementary techniques, making it accessible to beginners and students. Moreover, I will explain what kind of functoriality can be expected from a nerve theorem in general and describe a framework that allows one to prove a variety of functorial nerves theorems using modern homotopy theory. If time permits, I will showcase some counterexamples that illustrate the tightness of our statements.

This is based on joint work with Ulrich Bauer, Michael Kerber, and Alexander Rolle: https://arxiv.org/abs/2203.03571.

13:00 (EDT) / 18:00 (CET): Abhishek Rathod

Title: Approximation of the multicover bifiltration

Abstract: For a finite point set P \subset R^d, let M_{r,k} denote the set of points in R^d that are within distance r of at least k points in P. Allowing r and k to vary yields a 2-parameter family of spaces M, called the multicover bifiltration of P. It is a density-sensitive extension of the union-of-balls filtration commonly considered in TDA. It is robust to outliers in a strong sense, which motivates the problem of efficiently computing it (up to homotopy). A recent algorithm of Edelsbrunner and Osang computes a polyhedral model of M called the rhomboid bifiltration. In this work, we introduce an approximation of M (up to homotopy) which extends a version of the rhomboid tiling, and devise an efficient algorithm to compute it.

The talk is based on joint work with Uli Bauer, Tamal Dey and Michael Lesnick.