Itai Boneh
YOU?
Author Swipe
View article: The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$ Open
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 maintaining the LZ77 factorization of a dynamic string. By …
View article: Hamming Distance Oracle
Hamming Distance Oracle Open
In this paper, we present and study the \emph{Hamming distance oracle problem}. In this problem, the task is to preprocess two strings $S$ and $T$ of lengths $n$ and $m$, respectively, to obtain a data-structure that is able to answer quer…
View article: String 2-Covers with No Length Restrictions
String 2-Covers with No Length Restrictions Open
A $λ$-cover of a string $S$ is a set of strings $\{C_i\}_1^λ$ such that every index in $S$ is contained in an occurrence of at least one string $C_i$. The existence of a $1$-cover defines a well-known class of quasi-periodic strings. Quasi…
View article: Hairpin Completion Distance Lower Bound
Hairpin Completion Distance Lower Bound Open
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 hairpin completion operation transforms a string $S$ into …
View article: Searching 2D-Strings for Matching Frames
Searching 2D-Strings for Matching Frames Open
We introduce the natural notion of a matching frame in a $2$-dimensional string. A matching frame in a $2$-dimensional $n\times m$ string $M$, is a rectangle such that the strings written on the horizontal sides of the rectangle are identi…
View article: Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings
Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings Open
We give an $\tilde O(n^2)$ time algorithm for computing the exact Dynamic Time Warping distance between two strings whose run-length encoding is of size at most $n$. This matches (up to log factors) the known (conditional) lower bound, and…
View article: Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs Open
In vertex-cut sparsification, given a graph $G=(V,E)$ with a terminal set $T\subseteq V$, we wish to construct a graph $G'=(V',E')$ with $T\subseteq V'$, such that for every two sets of terminals $A,B\subseteq T$, the size of a minimum $(A…
View article: Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time
Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time Open
The Suffix Array $SA_S[1\ldots n]$ of an $n$-length string $S$ is a lexicographically sorted array of the suffixes of $S$. The suffix array is one of the most well known and widely used data structures in string algorithms. We present a da…
View article: The k-Mappability Problem Revisited
The k-Mappability Problem Revisited Open
The k-mappability problem has two integers parameters m and k. For every subword of size m in a text S, we wish to report the number of indices in S in which the word occurs with at most k mismatches. The problem was lately tackled by Alza…
View article: Update Query Time Trade-off for dynamic Suffix Arrays
Update Query Time Trade-off for dynamic Suffix Arrays Open
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 data structures, and it functions as a key tool in many strin…
View article: Analysis of the Period Recovery Error Bound
Analysis of the Period Recovery Error Bound Open
The recovery problem is the problem whose input is a corrupted text T that was originally periodic, and where one wishes to recover its original period. The algorithm’s input is T without any information about either the period’s length or…
View article: Update Query Time Trade-Off for Dynamic Suffix Arrays
Update Query Time Trade-Off for Dynamic Suffix Arrays Open
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 data structures, and it functions as a key tool in many string …
View article: Dynamic Palindrome Detection
Dynamic Palindrome Detection Open
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 has been reached. In this paper we examine another classic st…
View article: Repetition Detection in a Dynamic String
Repetition Detection in a Dynamic String Open
A string UU for a non-empty string U is called a square. Squares have been well-studied both from a combinatorial and an algorithmic perspective. In this paper, we are the first to consider the problem of maintaining a representation of th…
View article: Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms
Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms Open
There has been recent interest in dynamic string algorithms, i.e. string problems where the input changes dynamically. One such problem is the longest common factor (LCF) problem. It is well known that the LCF of two strings S and D of len…