Persistence Meets Resistance: Doubling Down on Hardness
We present results on the approximate computation of stable invariants for filtrations of finite metric spaces in the context of persistent homology. We establish novel approximation algorithms in the setting of $n$-point metric spaces where the growth of the doubling dimension is in $o(\log n)$ and the diameter is bounded. In the $1$-parameter case, by revisiting known techniques (greedy permutations) in a new way, we derive the first linear-time algorithms for the problem of computing additive $\varepsilon$-approximations of any stable barcode. By deriving bounds on the convergence rate…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.27269
curl -X POST /api/v1/records/arxiv/2608.27269/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27269/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'