The complexity of some topological inference problems

DOI10.1007/s10208-013-9152-1zbMath1308.68060OpenAlexW2033733997MaRDI QIDQ486691

Shmuel Weinberger

Publication date: 16 January 2015

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-013-9152-1

zbMATH Keywords

entropydimensionhomologylower boundshomeomorphismconcentration of measureinferencesample complexitydetecting singularities for a polyhedronGromov-Hausdorff spacetopological type of a manifold

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Polytopes and polyhedra (52B99) Nonparametric inference (62G99) PL-topology (57Q99)

Related Items

Stabilizing the unstable output of persistent homology computations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric inference for probability measures
• Stability of persistence diagrams
• A sampling theory for compact sets in Euclidean space
• Fitting a \(C^m\)-smooth function to data. II
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Hyperbolic structures on 3-manifolds. I: Deformation of acylindrical manifolds
• Surface reconstruction by Voronoi filtering
• Counting hyperbolic manifolds
• 3-manifolds with(out) metrics of nonpositive curvature
• Geometry of the space of triangulations of a compact manifold
• On the curvature of piecewise flat spaces
• Finding the homology of submanifolds with high confidence from random samples
• Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees
• Counting hyperbolic manifolds with bounded diameter
• Persistent Homology: Theory and Practice
• Betti numbers are testable
• A Topological View of Unsupervised Learning from Noisy Data
• Topology and data
• Knots are Determined by Their Complements
• Topology for Computing
• Barcodes: The persistent topology of data
• Manifold reconstruction in arbitrary dimensions using witness complexes