3 citations · 6 across the 15 of their papers we have counts for
16 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…
Dynamic Time Warping in the Low-Distance Regime
Itai Boneh, Shay Golan, Tomasz Kociumaka
Dynamic Time Warping (DTW) is a classical similarity measure for strings and time series that allows local stretching. Given non-empty strings over an alphabet and a cost…
Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries
Dominik Kempa, Tomasz Kociumaka
For a text of length over an alphabet of size , its suffix array lists the starting positions of the suffixes of in lexicographic order, and its inverse suffix array…
Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes
Dominik Kempa, Tomasz Kociumaka
For a text with , its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suf…
Tight Lower Bounds for Central String Queries in Compressed Space
Dominik Kempa, Tomasz Kociumaka
In this work, we study the limits of compressed data structures, i.e., structures that support various queries on an input text using space proportional to the size of $T…
Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
Dominik Kempa, Tomasz Kociumaka
We study the fundamental question of how efficiently suffix array entries can be accessed when the array cannot be stored explicitly. The suffix array of a text of…
Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
We present the first dynamic algorithms for Dyck and tree edit distances with subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a well-pa…
Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
Tomasz Kociumaka, Ali Shahali
The tree edit distance is a natural dissimilarity measure between rooted ordered trees whose nodes are labeled over an alphabet . It is defined as the minimum number of node edi…
Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
Itai Boneh, Egor Gorbachev, Tomasz Kociumaka
The edit distance of two strings is the minimum number of character edits (insertions, deletions, and substitutions) needed to transform into . Its we…
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Dominik Kempa, Tomasz Kociumaka
Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string from left to right into blocks (called phrases) so that each ph…
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
Paweł Gawrychowski, Egor Gorbachev, Tomasz Kociumaka
Min-plus matrix multiplication is used in many problems operating on distances in graphs or solvable by dynamic programming. Assuming the APSP hypothesis, there is no subcubic-time…
Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
Egor Gorbachev, Tomasz Kociumaka
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions needed to transform one string into the other. The textbook algorithm determines…
Faster Sublinear-Time Edit Distance
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation al…
Bellman-Ford is optimal for shortest hop-bounded paths
Tomasz Kociumaka, Adam Polak
This paper is about the problem of finding a shortest - path using at most edges in edge-weighted graphs. The Bellman--Ford algorithm solves this problem in time,…
How Compression and Approximation Affect Efficiency in String Distance Measures
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln +1
Real-world data often comes in compressed form. Analyzing compressed data directly (without decompressing it) can save space and time by orders of magnitude. In this work, we focus…
Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
Tomasz Kociumaka, Barna Saha
Given a context free language over alphabet and a string , {\em the language edit distance} problem seeks the minimum number of edits (insertions, d…