Computing the interleaving distance is NP-hard

DOI10.1007/s10208-019-09442-yzbMath1460.55006arXiv1811.09165OpenAlexW2989179987MaRDI QIDQ2216251

Yanyan Li

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

zbMATH Keywords

NP-hardnesspersistent homologymatrix completion problemsinterleavings

Mathematics Subject Classification ID

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