Itai Boneh

activity

20212024

most citedOptimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs

1 citations · 1 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DS2024

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 $S$ and $T$ of lengths $n$ and $m$ , respectiv…

cs.DS2022★ 1 cited

Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs

Itai Boneh, Robert Krauthgamer

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 se…

cs.DS2021

Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time

Amihood Amir, Itai Boneh

The Suffix Array $S A_{S} [1 \dots 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…