2 citations · 2 across the 7 of their papers we have counts for
15 papers · 1 filter
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.…
Õ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…