Hardness results for homology localization

DOI10.1007/s00454-010-9322-8zbMath1218.68084OpenAlexW3138338816MaRDI QIDQ633215

Chao Chen, Daniel Z. Freedman

Publication date: 31 March 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-010-9322-8

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Homology and cohomology theories in algebraic topology (55N99) Realizing cycles by submanifolds (57R95)

Related Items (10)

Cliques and cavities in the human connectome ⋮ A higher-dimensional homologically persistent skeleton ⋮ Volume-Optimal Cycle: Tightest Representative Cycle of a Generator in Persistent Homology ⋮ Stable volumes for persistent homology ⋮ A heuristic for short homology basis of digital objects ⋮ Multiscale projective coordinates via persistent cohomology of sparse filtrations ⋮ Tri-partitions and bases of an ordered complex ⋮ Computational topology and the Unique Games Conjecture ⋮ The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex ⋮ Lexicographic optimal homologous chains and applications to point cloud triangulations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Measuring and computing natural generators for homology groups
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Optimally cutting a surface into a disk
• Coverage in sensor networks via persistent homology
• Finding the homology of submanifolds with high confidence from random samples
• Reductions, completeness and the hardness of approximability
• Optimal homologous cycles, total unimodularity, and linear programming
• Topology and data
• Minimum-diameter covering problems
• Quantifying Homology Classes
• Homology flows, cohomology cuts
• Minimum cuts and shortest homologous cycles
• Approximating loops in a shortest homology basis from point data
• AN ALGEBRAIC TOPOLOGICAL METHOD FOR FEATURE IDENTIFICATION

This page was built for publication: Hardness results for homology localization