6 papers · 1 filter
Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic
Bingbing Hu, Tomasz Kociumaka, Jakob Nogler +1
Tree edit distance (TED), the analog of string edit distance (ED) for hierarchical data, is the minimum number of node insertions, deletions, and substitutions transforming one lab…
Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time
Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams
In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in…
The Cost of Changing Edges for Diameter Computation and More
Sam Hiken, Yael Kirkpatrick, Jakob Nogler +1
The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time mo…
The Communication Complexity of Pattern Matching with Edits Revisited
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
In the decades-old Pattern Matching with Edits problem, given a length- string (the text), a length- string (the pattern), and a positive integer (the threshold),…
Hardness of Dynamic Tree Edit Distance and Friends
Bingbing Hu, Jakob Nogler, Barna Saha
String Edit Distance is a more-than-classical problem whose behavior in the dynamic setting, where the strings are updated over time, is well studied. A single-character substituti…
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Jakob Nogler, Adam Polak, Barna Saha +3
The tree edit distance (TED) between two rooted ordered trees with nodes labeled from an alphabet is the minimum cost of transforming one tree into the other by a sequence…