On the public citation graph

Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)

https://doi.org/10.1145/3381878
0 signed · 87 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/jcss.1997.1388openalex-snapshot
On the Exponent of the All Pairs Shortest Path Problem
inferredcites →https://doi.org/10.1007/11940128_11openalex-snapshot
Approximating Tree Edit Distance Through String Edit Distance
inferredcites →https://doi.org/10.1007/3-540-68530-8_8openalex-snapshot
Computing the Edit-Distance Between Unrooted Ordered Trees
inferredcites →https://doi.org/10.1007/978-3-540-28639-4_25openalex-snapshot
Space and Time Complexity of Exact Algorithms: Some Open Problems
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_1openalex-snapshot
Exact Weight Subgraphs and the k-Sum Conjecture
inferredcites →https://doi.org/10.1007/978-3-662-43948-7_10openalex-snapshot
On Hardness of Jumbled Indexing
inferredcites →https://doi.org/10.1007/978-3-662-43948-7_4openalex-snapshot
Consequences of Faster Alignment of Sequences
inferredcites →https://doi.org/10.1007/bf00264289openalex-snapshot
Optimum binary search trees
inferredcites →https://doi.org/10.1007/s00453-010-9401-5openalex-snapshot
On Dynamic Shortest Paths Problems
inferredcites →https://doi.org/10.1016/0020-0190(77)90064-3openalex-snapshot
The tree-to-tree editing problem
inferredcites →https://doi.org/10.1016/0031-3203(94)00109-yopenalex-snapshot
Algorithms for the constrained editing distance between ordered labeled trees and related problems
inferredcites →https://doi.org/10.1016/0196-6774(90)90011-3openalex-snapshot
Fast algorithms for the unit cost editing distance between trees
inferredcites →https://doi.org/10.1016/b978-012722442-8/50021-5openalex-snapshot
Path Queries on Compressed XML
inferredcites →https://doi.org/10.1016/j.dam.2007.03.023openalex-snapshot
Open problems around exact algorithms
inferredcites →https://doi.org/10.1016/j.tcs.2004.05.009openalex-snapshot
On the complexity of fixed parameter clique and dominating set
inferredcites →https://doi.org/10.1016/j.tcs.2004.12.030openalex-snapshot
A survey on tree edit distance and related problems
inferredcites →https://doi.org/10.1016/j.tcs.2005.09.023openalex-snapshot
A new algorithm for optimal 2-constraint satisfaction and its implications
inferredcites →https://doi.org/10.1016/j.tcs.2015.03.026openalex-snapshot
On hardness of several string indexing problems
inferredcites →https://doi.org/10.1016/s0167-8655(02)00382-3openalex-snapshot
Comparison of AESA and LAESA search algorithms using string and tree-edit-distances
inferredcites →https://doi.org/10.1017/cbo9780511574931openalex-snapshot
Algorithms on Strings, Trees and Sequences
inferredcites →https://doi.org/10.1093/bioinformatics/6.4.309openalex-snapshot
Comparing multiple RNA secondary structures using tree comparisons
inferredcites →https://doi.org/10.1093/oso/9780195113679.001.0001openalex-snapshot
Pattern Matching Algorithms
inferredcites →https://doi.org/10.1109/focs.2010.67openalex-snapshot
Subcubic Equivalences between Path, Matrix and Triangle Problems
inferredcites →https://doi.org/10.1109/focs.2014.53openalex-snapshot
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems
inferredcites →https://doi.org/10.1109/focs.2014.76openalex-snapshot
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails
inferredcites →https://doi.org/10.1109/focs.2015.14openalex-snapshot
Tight Hardness Results for LCS and Other Sequence Similarity Measures
inferredcites →https://doi.org/10.1109/focs.2015.15openalex-snapshot
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
inferredcites →https://doi.org/10.1109/focs.2015.16openalex-snapshot
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
inferredcites →https://doi.org/10.1109/focs.2016.48openalex-snapshot
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product
inferredcites →https://doi.org/10.1109/focs.2016.56openalex-snapshot
Which Regular Expression Patterns Are Hard to Match?
inferredcites →https://doi.org/10.1109/focs.2016.58openalex-snapshot
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
inferredcites →https://doi.org/10.1109/iciap.1999.797676openalex-snapshot
Region-based modeling and tree edit distance as a basis for gesture recognition
inferredcites →https://doi.org/10.1137/0218082openalex-snapshot
Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
inferredcites →https://doi.org/10.1137/09076619xopenalex-snapshot
Finding, Minimizing, and Counting Weighted Subgraphs
inferredcites →https://doi.org/10.1137/1.9781611973730.112openalex-snapshot
Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
inferredcites →https://doi.org/10.1137/1.9781611974331.ch88openalex-snapshot
Subtree Isomorphism Revisited
inferredcites →https://doi.org/10.1137/1.9781611974782.69openalex-snapshot
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
inferredcites →https://doi.org/10.1145/1613676.1613680openalex-snapshot
Compressing and indexing labeled trees, with applications
inferredcites →https://doi.org/10.1145/1644015.1644017openalex-snapshot
An optimal decomposition algorithm for tree edit distance
inferredcites →https://doi.org/10.1145/2591796.2591811openalex-snapshot
Faster all-pairs shortest paths via circuit complexity
inferredcites →https://doi.org/10.1145/2699485openalex-snapshot
Efficient Computation of the Tree Edit Distance
inferredcites →https://doi.org/10.1145/2746539.2746594openalex-snapshot
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
inferredcites →https://doi.org/10.1145/2746539.2746612openalex-snapshot
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
inferredcites →https://doi.org/10.1145/2897518.2897653openalex-snapshot
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
inferredcites →https://doi.org/10.1145/3186893openalex-snapshot
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
inferredcites →https://doi.org/10.1145/321796.321811openalex-snapshot
The String-to-String Correction Problem
inferredcites →https://doi.org/10.1145/322139.322143openalex-snapshot
The Tree-to-Tree Correction Problem
inferredcites →https://doi.org/10.1145/322290.322295openalex-snapshot
Pattern Matching in Trees
inferredcites →https://doi.org/10.1145/3414845openalex-snapshot
Fine-grained Complexity Analysis of Two Classic TSP Variants
inferredcites →https://doi.org/10.2307/2534039openalex-snapshot
Introduction to Computational Biology: Maps, Sequences and Genomes.
inferredcites →https://doi.org/10.4230/lipics.icalp.2016.81openalex-snapshot
Tight Hardness Results for Maximum Weight Rectangles
inferredcites →https://doi.org/10.48550/arxiv.1607.04229openalex-snapshot
Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
inferredcites →https://doi.org/10.5860/choice.36-1021openalex-snapshot
Pattern matching algorithms

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-81885-2_2openalex-snapshot
Algorithmic Techniques
inferred← citeshttps://doi.org/10.1007/978-3-031-20643-6_21openalex-snapshot
On the Hardness of Computing the Edit Distance of Shallow Trees
inferred← citeshttps://doi.org/10.1007/978-3-031-55598-5_13openalex-snapshot
Faster Combinatorial k-Clique Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-031-79029-4_26openalex-snapshot
Embedding Representations for AutoML Pipelines
inferred← citeshttps://doi.org/10.1007/978-3-032-21997-8_20openalex-snapshot
Measuring Originality in Computer Programming: A Code Distance Approach
inferred← citeshttps://doi.org/10.1016/j.asoc.2021.107852openalex-snapshot
Similarity-evaluation-based evolving of flexible neural trees for imbalanced classification
inferred← citeshttps://doi.org/10.1016/j.dam.2023.01.003openalex-snapshot
Inexact tree pattern matching with 1-degree edit distance using finite automata
inferred← citeshttps://doi.org/10.1016/j.ipl.2023.106358openalex-snapshot
Improved bounds for rectangular monotone Min-Plus Product and applications
inferred← citeshttps://doi.org/10.1016/j.patrec.2023.02.017openalex-snapshot
The edge-preservation similarity for comparing rooted, unordered, node-labeled trees
inferred← citeshttps://doi.org/10.1016/j.tcs.2025.115433openalex-snapshot
Partial permutations comparison, maintenance and applications
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00082openalex-snapshot
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00034openalex-snapshot
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00071openalex-snapshot
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00088openalex-snapshot
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00135openalex-snapshot
Optimal Algorithms for Bounded Weighted Edit Distance
inferred← citeshttps://doi.org/10.1109/topoinvis60193.2023.00015openalex-snapshot
Taming Horizontal Instability in Merge Trees: On the Computation of a Comprehensive Deformation-Based Edit Distance
inferred← citeshttps://doi.org/10.1117/12.3003797openalex-snapshot
A multi-threaded virtual DOM difference method based on web worker
inferred← citeshttps://doi.org/10.1134/s1064562424702259openalex-snapshot
An Exact Quadratic Algorithm for the Shortest Tree Transformation
inferred← citeshttps://doi.org/10.1137/1.9781611975031.80openalex-snapshot
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
inferred← citeshttps://doi.org/10.1137/22m1480719openalex-snapshot
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
inferred← citeshttps://doi.org/10.1145/3517804.3526234openalex-snapshot
Tight Fine-Grained Bounds for Direct Access on Join Queries
inferred← citeshttps://doi.org/10.1145/3519935.3520032openalex-snapshot
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
inferred← citeshttps://doi.org/10.1145/3564246.3585178openalex-snapshot
Weighted Edit Distance Computation: Strings, Trees, and Dyck
inferred← citeshttps://doi.org/10.1145/3581783.3611845openalex-snapshot
SkipStreaming: Pinpointing User-Perceived Redundancy in Correlated Web Video Streaming through the Lens of Scenes
inferred← citeshttps://doi.org/10.1145/3618260.3649663openalex-snapshot
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
inferred← citeshttps://doi.org/10.1145/3618260.3649696openalex-snapshot
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
inferred← citeshttps://doi.org/10.1145/3717823.3718116openalex-snapshot
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
inferred← citeshttps://doi.org/10.1145/3717823.3718240openalex-snapshot
All-Pairs Shortest Paths with Few Weights per Node
inferred← citeshttps://doi.org/10.14778/3654621.3654634openalex-snapshot
X-TED: Massive Parallelization of Tree Edit Distance
inferred← citeshttps://doi.org/10.31857/s2686954324050058openalex-snapshot
AN EXACT QUADRATIC ALGORITHM FOR THE SHORTEST TREE TRANSFORMATION
inferred← citeshttps://doi.org/10.3233/atde230301openalex-snapshot
Geological Paleontological Code Matching Method Based on Edit Distance Algorithm
inferred← citeshttps://doi.org/10.3390/math11234847openalex-snapshot
A Secure Multi-Party Computation Protocol for Graph Editing Distance against Malicious Attacks
inferred← citeshttps://doi.org/10.48550/arxiv.1805.08554openalex-snapshot
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
inferred← citeshttps://doi.org/10.48550/arxiv.2105.02428openalex-snapshot
Faster Algorithms for Bounded Tree Edit Distance
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.