Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes
summary
The gist
We give randomized algorithms for 3-approximate edit distance in Oe(N(11/6)) time for unweighted edit distance and in Oe(N(40/21)) time for arbitrary metric edit weights…
In short
The paper presents randomized algorithms for finding a 3-approximate edit distance between strings, achieving Oe(N^(11/6)) time for unweighted costs and Oe(N^(40/21)) time for arbitrary metric weights. It introduces a routing idea using centers to source blocks, allowing efficient handling of both unit costs and weighted distances.
Key concepts
- Unit-Cost Approximation
- This method guarantees a factor three approximation with no additive error in Oe((n + m)^(11/6)) time. It works by dividing the source string into smaller blocks and using a routing strategy based on intermediate 'centers' to estimate distances between blocks and target substrings, leveraging the triangle inequality of edit distance.
- Metric-Weighted Approximation
- This algorithm finds an alignment for strings with arbitrary metric costs in Oe((n + m)^(40/21)) time. It combines the center-correcting idea with DIST-matrix machinery to efficiently reuse preprocessing, allowing it to achieve a 3-approximation for weighted edit distances with high probability.
- Source Blocks and Centers
- The source string is partitioned into consecutive 'source blocks' of limited length. A small set of 'centers' strings are computed against these blocks and target substrings. This partitioning allows the algorithm to use localized distance estimates, simplifying the overall computation by avoiding full preprocessing against the entire target string.
- Hardness Results
- The paper establishes lower bounds showing that achieving certain approximation factors for non-metric costs requires a high number of oracle queries (Ω(N^2)). For constant-size alphabets, it uses the Orthogonal Vectors Hypothesis to show no faster than O(N^(2-δ)) time algorithm exists for symmetric weights.
Terminology used across episodes
This episode discusses
- Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes · Paper Radio
- Deterministic Longest Common Subsequence Approximation in Near-Linear Time
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Which Regular Expression Patterns are Hard to Match?
- Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems
- Does Preprocessing help in Fast Sequence Comparisons?
- Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
- Semi-local string comparison: algorithmic techniques and applications
The paper
Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes · Read on arXiv
ETH Zurich · Max Planck Institute for Informatics
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Edit Distance Approximation".
Jane: Here's the gist of the paper. We give randomized algorithms for 3-approximate edit distance in Oe(N(11/6)) time for unweighted edit distance and in Oe(N(40/21)) time for arbitrary metric edit weights, where N is the total input length For non-metric costs, we prove an unconditional omega(N 2) oracle-query lower bound for every approximation factor depending only on N, even for symmetric weights or weights satisfying the triangle inequality (but not both) Under the Orthogonal Vectors Hypothesis, we show a similar result for constant-size alphabets In contrast, for symmetric weights over a binary alphabet we show an Oe(N(40/21)) time 3-approximation algorithm.
Tom: Factor Three Approximation for Unit Costs The unit-cost approximation algorithm achieves a factor three guarantee with no additive error in Oe((n + m)(11/6)) time This is achieved by partitioning the source string X into consecutive substrings Ui, called source blocks, of length at most W = o(N) each.
Jane: The algorithm uses a routing idea where it computes distances from a small set C of intermediate strings called centers to all source blocks Ui and all substrings of Y.
Tom: By using the triangle inequality of edit distance, it claims that ed(Ui, Y[p..
Paper summary: Tom: So, to wrap up this discussion on "Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes", this paper presents randomized algorithms that give a factor three approximation for edit distance. They achieve big O of N eleven six over twelve time for unweighted edit distance and big O of N forty over twenty-one time for arbitrary metric weights.
Jane: The title itself points to the two main contributions: the subquadratic factor three approximation and the monge approximation schemes they introduce. Essentially, they figured out a way to use routing ideas with centers to get those good approximations in better than quadratic time when things aren't just simple character edits.
Lu: What this means for the world is that we can now handle more complex distance measures, like weighted costs, without immediately jumping into algorithms that take time scaling quadratically with the size of the strings. This opens up possibilities for sequence alignment in real-world bioinformatics or even complex data comparison tasks where errors aren't uniform.
Meng: From an engineering standpoint, it gives us a concrete path to deploying approximate solutions for metric edit distance on large datasets, provided we can manage that N forty over twenty-one runtime. It’s a specific performance target we can aim for in our development pipeline.
Tom: Exactly, and the paper also sets important lower bounds on the oracle query complexity, showing that without certain cost structures like symmetry or triangle inequality, you still face quadratic time hurdles for finding good approximations. That tells us what's fundamentally impossible without those structural assumptions.
Jane: So the paper gives us a very specific toolkit for balancing speed and accuracy in approximate edit distance, showing concrete runtime bounds and where the limitations of those tools lie when the cost functions aren't perfectly behaved.
Conclusion: Tom: So we're wrapping up on this paper about "Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes." It tackles how to get a good estimate of edit distance without needing a quadratic amount of time for huge strings.
Jane: Right, so they’ve got these randomized algorithms, right? They use some clever ideas involving partitioning the source string into blocks and using these intermediate centers to get an approximation that’s only three times the true distance.
Lu: That factor three approximation is achieved in time that scales like N eleven six over twelve for unweighted edit distance. It uses this routing idea where you compute distances from a few specific centers to all the parts of your target string.
Meng: For me, the real thing is that it handles metric costs too, not just simple character matches. The time complexity jumps up to N forty over twenty-one for those more complicated weight functions, which is still pretty manageable for production at scale.
Lalam: What they're showing here is that we can get a three times approximation with these specific runtime guarantees when you move past the simplest edit distance problems into things where the costs matter.
Tom: So what does this mean for us? It means we can handle more complex data comparisons on massive datasets without immediately hitting a wall of quadratic time.
Jane: It suggests that for many practical applications, especially in areas like bioinformatics where sequences are long, we don't have to settle for just a rough guess anymore.
Lu: The lower bounds they set are important too. They show that if you don't have certain mathematical properties on your costs—like symmetry or the triangle inequality—you can expect to face quadratic time hurdles again for these approximations.
Meng: That tells me we need to be careful about what kind of cost functions we choose for our real data, because if they don't fit those nice properties, the speed advantage disappears.
Tom: So basically, they give us a concrete tool that works well under specific conditions but warn us where those conditions are important for the performance to hold up.
Jane: And that leads into what’s next: we need to dig into those lower bounds and see exactly how much faster we can go if we relax some of those requirements.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game