CS Paper Radar

Persistence Meets Resistance: Doubling Down on Hardness

Benedikt Kolbe, Tim Mayr

cs.CC math.ATcs.CG ·submitted 2026-08-27 15:49 UTC · v1
top venue

Abstract

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 and the approximation quality of uniform samples, we extend the approach to selected multiparameter filtrations. We show that for normalized measure bifiltrations, including the multicover and subdivision-Rips bifiltration, any stable invariant can be probabilistically approximated in time constant in $n$. The constants in the running times of our algorithms depend on the doubling dimension, the diameter and the success probability. We further study the problem through the lens of fine-grained complexity and show that computing the rank of a matrix reduces to that of approximating the barcode of the Vietoris--Rips or Čech filtration. We present two variants of the reduction, one for sufficiently good additive approximations and the other for any constant factor multiplicative approximations.

Comment
Conference version published at ICALP 2026. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.131

Closest papers

Nearest neighbours by meaning across the whole index.

Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces

cs.DS cs.CGcs.DC ·2026-11-04 ·Eunjin Oh, Hyeonjun Shin
theory similarity 0.60
Abstract

We develop a unified algorithmic framework for computing approximate minimum spanning trees (MSTs) in metric spaces in the fully scalable Massively Parallel Computation (MPC) model. Using this framework, we obtain the following results for any fixed constant $σ\in(0,1)$: - General metrics: Given all pairwise distances, we compute a $(1+\varepsilon)$-approximate MST in $O(\log(1/\varepsilon))$ rounds using $n^σ$ local space per machine and $\widetilde{O}(n^2)$ total space. - Euclidean spaces: Given $n$ points in $\mathbb{R}^d$, we compute an $O(1/σ^4)$-approximate MST in $O(1)$ rounds using $(nd)^σ$ local space per machine and $O(nd+n^{1+σ})$ total space. - Doubling metrics: Given $n$ points in a metric of doubling dimension $\mathrm{ddim}=O(σ\log n)$, we compute an $O(1/σ)$-approximate MST in $O(\mathrm{ddim}/σ^4)$ rounds using $n^σ$ local space per machine and $\widetilde{O}(n^{1+σ})\cdot 2^{O(\mathrm{ddim})}$ total space. For any fixed constant $\varepsilon\in(0,1)$, these results give the first constant-round MPC algorithms achieving $(1+\varepsilon)$-approximation in general metrics and $O(1)$-approximation in a high-dimensional Euclidean space, respectively. They improve upon the $O(\log\log n+\log(1/\varepsilon))$-round algorithm for general metrics [SODA'25] and the $O(\log\log n\cdot\log\log\log n)$-round algorithm for Euclidean spaces [SODA'24], respectively. Moreover, our round complexity for general metrics is asymptotically optimal in its dependence on $\varepsilon$, matching the $Ω(\log(1/\varepsilon))$ lower bound of [SODA'25] under the 1-vs-2-cycles conjecture. Our result also answers an open question raised by [STOC'23].

0.18

Fast Metric Decompositions in High Dimension

cs.DS cs.CG ·2026-08-23 ·Robert Krauthgamer, Asaf Petruschka, Nir Petruschka
published similarity 0.59
Abstract · 17 pages

Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of $n$-point sets in $\ell_\infty$ and $\ell_2$ spaces of high dimension $d$. For $\ell_\infty$, we design a padded-decomposition algorithm that runs in time $\tilde{O}(nd^2)$, which is near-linear in $n$, and achieves padding parameter $\tilde{O}(\log n)$. Our algorithm constructs a new sparse neighborhood cover that is based on geometric properties of $\ell_\infty$ [Indyk, JCSS'01], and utilizes recent reductions between covers and decompositions [Conroy and Filtser, STOC'25]. For $\ell_2$, we design a separating-decomposition algorithm that achieves near optimal separation $\tilde{O}(\sqrt{\log n})$ in almost-linear time $n^{1+o(1)}$. Our bounds improve over known algorithms with similar running time by a factor $Ω(\sqrt{\log n})$, and the techniques have additional applications to spanners and nearest-neighbor search.

0.23

How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics

cs.DS ·2026-10-06 ·Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Chinmay Sonar +2 more
hot direction similarity 0.58
Abstract

Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most $k$ weights can be changed to form a metric. Motivated by metric repair for noisy data, the problem admits a polynomial-time $O(\log n)$-approximation due to Cohen-Addad, Fan, Lee and de Mesmay [SIAM J. Comput., 2025]. In the context of parameterized complexity, Fan, Gilbert, Raichel, Sonthalia and Van Buskirk [SWAT 2020] gave a $k^{O(k)}n^{O(1)}$-time algorithm. Fomin, Golovach and More [IPEC 2026] obtained an $O(k^2)$ kernel and a single-exponential algorithm for the ultrametric case. They asked whether general metrics admit a single-exponential algorithm and a polynomial kernel, and whether the tree-metric analogue is fixed-parameter tractable. We answer all three questions. We give a $2^{O(k)}n^{O(1)}$-time algorithm and prove that, unless ETH fails, no $2^{o(k)}n^{O(1)}$-time algorithm exists, even when all input distances lie in $\{1,2,3\}$. We also give a kernel with at most $6k$ vertices. The kernel supports solution lifting and can precede any approximation algorithm. Combined with the $O(\log n)$-approximation of Cohen-Addad, Fan, Lee and de Mesmay, it yields an $O(\log \mathrm{OPT})$-approximation at no asymptotic cost in running time. Both results extend to an interval generalization in which each edge $e$ has an observed value $M_e$ and an admissible range $[A_e,B_e]$ within which it may be reassigned; the kernel then has $7k$ vertices. Finally, Tree Metric Violation Distance is fixed-parameter tractable and solvable in $k^{O(k)}n^{O(1)}$ time.

0.48

A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics

cs.DS ·2026-09-14 ·Ethan Mader, Borna Tavasoli, Jihan Wang
similarity 0.57
Abstract

We study weighted edit distance between two strings of total length $n$, where edit costs are induced by an arbitrary metric. For equal-length inputs, Kuszmaul (2019) gave an $O(n^δ)$-approximation with $\widetilde{O}(n^{2-δ})$ running time for every fixed $0 < δ< 1$. We give the first constant-factor approximation for weighted edit distance over arbitrary metrics in strongly subquadratic running time. For every $0 < \varepsilon \le 1$, our randomized algorithm runs in $\widetilde{O}(n^{7/4}/\varepsilon^8)$ time and returns a $(3+\varepsilon)$-approximation with probability at least $1-n^{-10}$. The algorithm allows unequal input lengths and places no bound on the ratio between edit costs.

0.20

Near-Optimal Space and Time Cut Sparsification in Turnstile Streams

cs.DS ·2026-11-02 ·Honghao Lin, Vahab Mirrokni, David P. Woodruff
similarity 0.57
Abstract

A seminal result of Ahn, Guha, and McGregor (PODS'12) showed that a cut sparsifier of an unweighted graph can be computed from a near-linear number of linear measurements. Later work extended this to spectral sparsifiers (Kapralov et al., FOCS'14) and to near-linear recovery time (Kapralov et al., SODA'20). For weighted graphs, these sketches rely on grouping edges by weight, which general turnstile streams do not allow. Chen, Khanna, and Li (FOCS'22) removed this limitation, using $\tilde{O}(n/\varepsilon^3)$ bits of space. We improve the space to $\tilde{O}(n/\varepsilon^2)$ bits. Our algorithm makes one pass over a general turnstile stream of a weighted graph, processes each update in $\tilde{O}(1)$ time, and recovers, in $\tilde{O}(n/\varepsilon^2)$ time, a reweighted subgraph with $O(n\varepsilon^{-2}\log^2 n)$ edges that preserves every cut within a factor of $1\pm\varepsilon$. Its space, update time, and recovery time are all optimal up to polylogarithmic factors.

0.24

The sublevel Flood bifiltration: towards scalable 2-parameter persistent homology

cs.CG math.ATcs.LG ·2026-10-04 ·Mattéo Clémot, Julie Digne, Julien Tierny
similarity 0.57
Abstract

Multiparameter persistent homology is a rapidly developing branch of topological data analysis that improves the robustness of single-parameter persistent homology to outliers, while still capturing the metric characteristics of the data. However, a notable limitation is its lack of scalability. In this paper, we introduce a novel approach for efficiently computing 2-parameter persistent homology on large point sets. Our work extends the Flood filtration, originally developed for single-parameter persistence. Our construction, called the sublevel Flood bifiltration, offers a scalable approximation of the sublevel offset bifiltration. We show that it benefits from theoretical stability properties and describe how to compute it efficiently. We demonstrate the performance of our approach in classification tasks on low-dimensional synthetic datasets, where density awareness is critical, as well as on real-world time series datasets.

0.28

A Nearly Optimal Min-Cut Algorithm for Dynamic Streams

cs.DS ·2026-10-25 ·Yang P. Liu, Hoai-An Nguyen, Vihan Shah, David P. Woodruff
similarity 0.57
Abstract

We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same $\tilde{O}(n/\varepsilon)$ space bound for insertion-only streams, while prior to our work the best known bound even for unweighted dynamic streams was $\tilde{O}(n/\varepsilon^2)$, due to Ahn, Guha, and McGregor (PODS 2012). Our main technical contribution is an $\tilde{O}(n/\varepsilon)$-space for-each cut sketch in dynamic streams, which may be of independent interest. The construction applies to weighted graphs under general $\pmΔ$ updates, a stronger model than the standard dynamic-stream setting in which weighted edges are inserted and deleted in their entirety. Despite this stronger guarantee, our algorithm is surprisingly simple and relies on very little machinery. We also obtain applications to minimum $\ell_p$-norm $k$-partitioning for every fixed $k$, weighted correlation-clustering evaluation for two clusters, and for-each cut sketching in balanced directed graphs.

0.45

Subexponential Algorithms for Continuous Euclidean $k$-Means in Subpolylogarithmic Dimension

cs.CG cs.DS ·2026-11-19 ·Junqi Tan
similarity 0.57
Abstract · 22 pages

Given $n$ points in $\mathbb{Q}^d$ and an integer $k$, the continuous Euclidean $k$-means problem asks for $k$ centers in $\mathbb{R}^d$ that minimize the sum of squared distances from the input points to their nearest centers. In one dimension, the problem can be solved in polynomial time by dynamic programming. In higher dimensions, the algorithm of Inaba, Katoh, and Imai [SoCG 1994] runs in polynomial time when both $k$ and $d$ are fixed. Mahajan, Nimbhorkar, and Varadarajan [TCS 2012] showed that the problem is NP-hard even in the plane when $k$ is part of the input, answering a question of Dasgupta [2008]. In this paper, we give a deterministic exact algorithm for continuous Euclidean $k$-means. For arbitrary $k$ and $d=(\log n)^{o(1)}$, the algorithm runs in $O^*(2^{o(n)})$ time and uses polynomial space. Aman, Karthik C. S., and Punna [ESA 2024] asked whether the $2^n$ time bound for Euclidean $k$-means can be improved in high dimensions. Our result gives an affirmative answer to the corresponding question in subpolylogarithmic dimension.

0.29