From the 1 of 7 linked papers with an AI index.
7 papers
Random Access to LZ-End: Faster and Deterministic
Itai Boneh, PaweÅ Gawrychowski
The paper presents a deterministic, O(z)-space data structure for LZ-End compressed strings that supports random access and substring extraction queries in polylogarithmic time, wi…
Balancing Two-Dimensional Straight-Line Programs
Itai Boneh, Estéban Gabory, PaweŠGawrychowski +1
We consider building, given a straight-line program (SLP) consisting of productions deriving a two-dimensional string of size , a structure capable of providing…
The Complexity of Dynamic LZ77 is
Itai Boneh, Shay Golan, Matan Kraus
The Lempel-Ziv 77 (LZ77) factorization is a fundamental compression scheme widely used in text processing and data compression. In this work, we investigate the time complexity of…
Deterministic Longest Common Subsequence Approximation in Near-Linear Time
Itai Boneh, Shay Golan, Matan Kraus
We provide a deterministic algorithm that outputs an -approximation for the Longest Common Subsequence (LCS) of two input sequences of length in near-linear…
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…
Ãptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
Itai Boneh, Shiri Chechik, Shay Golan +2
We present a labeling scheme that assigns labels of size to the vertices of a directed weighted planar graph , such that for any fixed from the lab…