Computing the interleaving distance is NP-hard
From MaRDI portal
Publication:2216251
DOI10.1007/s10208-019-09442-yzbMath1460.55006arXiv1811.09165OpenAlexW2989179987MaRDI QIDQ2216251
Publication date: 15 December 2020
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.09165
Persistent homology and applications, topological data analysis (55N31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matrix completion problems (15A83)
Related Items (10)
Multiparameter Persistence Landscapes ⋮ Thickening of the diagonal and interleaving distance ⋮ Spatiotemporal persistent homology for dynamic metric spaces ⋮ Unnamed Item ⋮ On the stability of interval decomposable persistence modules ⋮ On the geometrical properties of the coherent matching distance in 2D persistent homology ⋮ The reflection distance between zigzag persistence modules ⋮ Generalized persistence algorithm for decomposing multiparameter persistence modules ⋮ Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology ⋮ Algebraic homotopy interleaving distance
Cites Work
- Unnamed Item
- Unnamed Item
- Testing isomorphism of modules.
- Algebraic stability of zigzag persistence modules
- Multidimensional persistence and noise
- The theory of the interleaving distance on multidimensional persistence modules
- The Structure and Stability of Persistence Modules
- Decoding of Neural Data Using Cohomological Feature Extraction
- Geometry Helps to Compare Persistence Diagrams
- Induced Matchings of Barcodes and the Algebraic Stability of Persistence
- Computational Complexity of the Interleaving Distance
- Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension
- Deterministic Polynomial Time Algorithms for Matrix Completion Problems
- Persistence-Based Clustering in Riemannian Manifolds
This page was built for publication: Computing the interleaving distance is NP-hard