6 papers
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…
String Problems in the Congested Clique Model
Shay Golan, Matan Kraus
In this paper we present algorithms for several string problems in the Congested Clique model. In the Congested Clique model, nodes (computers) are used to solve some problem.…
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…
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…