Source author record

Itai Boneh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs

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,B)$ -vertex-cut in $G'$ is the same as in $G$ . In the most basic setting, $G$ is unweighted and undirected, and we wish to bound the size of $G'$ by a function of $k=|T|$ . Kratsch and Wahlström [JACM 2020] proved that every graph $G$ (possibly directed), admits a vertex-cut sparsifier $G'$ with $O(k^3)$ vertices, which can in fact be constructed in randomized polynomial time. We study (possibly directed) graphs $G$ that are quasi-bipartite, i.e., every edge has at least one endpoint in $T$ , and prove that they admit a vertex-cut sparsifier with $O(k^2)$ edges and vertices, which can in fact be constructed in deterministic polynomial time. In fact, this bound naturally extends to all graphs with a small separator into bounded-size sets. Finally, we prove information-theoretically a nearly-matching lower bound, i.e., that $\tildeΩ(k^2)$ edges are required to sparsify quasi-bipartite undirected graphs.

preprint2020arXiv

Update Query Time Trade-off for dynamic Suffix Arrays

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 algorithms. In this paper, we present a data structure for maintaining the Suffix Array of a dynamic string. For every $0 \leq \varepsilon \leq 1$ , our data structure reports SA[i] in $\tilde{O}(n^{\varepsilon})$ time and handles text modification in $\tilde{O}(n^{1-\varepsilon})$ time. Additionally, our data structure enables the same query time for reporting iSA[i], with iSA being the Inverse Suffix Array of S[1 ... n]. Our data structure can be used to construct sub-linear dynamic variants of static strings algorithms or data structures that are based on the Suffix Array and the Inverse Suffix Array.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.