3 papers
cs.DS2025
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…
cs.DS2025
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…
cs.DS2025
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.…