8 papers
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 $…
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…
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…
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 ed…
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 w…