1 citations · 2 across the 10 of their papers we have counts for
18 papers
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…
Random Access to LZ-End: Faster and Deterministic
Itai Boneh, Paweł Gawrychowski
The LZ-End parsing of a length- string is a variation of Lempel-Ziv compression introduced by Kreft and Navarro [DCC 2010], motivated by the lack of a linear-size structure with…
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…
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 we…
Õ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…
Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
Itai Boneh, Shay Golan, Shay Mozes +2
We show how to preprocess a weighted undirected -vertex planar graph in time, such that the distance between any pair of vertices can then be reported in $\t…
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…
Hamming Distance Oracle
Itai Boneh, Dvir Fried, Shay Golan +1
In this paper, we present and study the \emph{Hamming distance oracle problem}. In this problem, the task is to preprocess two strings and of lengths and , respectiv…
String 2-Covers with No Length Restrictions
Itai Boneh, Shay Golan, Arseny Shur
A -cover of a string is a set of strings such that every index in is contained in an occurrence of at least one string . The existence of a -cover…
Hairpin Completion Distance Lower Bound
Itai Boneh, Dvir Fried, Shay Golan +1
Hairpin completion, derived from the hairpin formation observed in DNA biochemistry, is an operation applied to strings, particularly useful in DNA computing. Conceptually, a right…
Searching 2D-Strings for Matching Frames
Itai Boneh, Dvir Fried, Shay Golan +3
We introduce the natural notion of a matching frame in a -dimensional string. A matching frame in a -dimensional string , is a rectangle such that the strings…
Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings
Itai Boneh, Shay Golan, Shay Mozes +1
We give an time algorithm for computing the exact Dynamic Time Warping distance between two strings whose run-length encoding is of size at most . This matches (…
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs
Itai Boneh, Robert Krauthgamer
In vertex-cut sparsification, given a graph with a terminal set , we wish to construct a graph with , such that for every two se…
Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time
Amihood Amir, Itai Boneh
The Suffix Array of an -length string is a lexicographically sorted array of the suffixes of . The suffix array is one of the most well known and widely…
The k-mappability problem revisited
Amihood Amir, Itai Boneh, Eitan Kondratovsky
The -mappability problem has two integers parameters and . For every subword of size in a text , we wish to report the number of indices in in which the word o…
Update Query Time Trade-off for dynamic Suffix Arrays
Amihood Amir, Itai Boneh
The Suffix Array SA(S) of a string S[1 ... n] is an array containing all the suffixes of S sorted by lexicographic order. The suffix array is one of the most well known indexing da…
Dynamic Palindrome Detection
Amihood Amir, Itai Boneh
Lately, there is a growing interest in dynamic string matching problems. Specifically, the dynamic Longest Common Factor problem has been researched and some interesting results ha…